StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>you could build a regular trie and add wildcard edges. then your complexity would be O(n) where n is the length of the pattern. You would have to replace runs of <code>**</code> with <code>*</code> in the pattern first (also an O(n) operation).</p> <p>If the list of words were <i>I am an ox</i> then the trie would look a bit like this:</p> <pre> (I ($ [I]) a (m ($ [am]) n ($ [an]) ? ($ [am an]) * ($ [am an])) o (x ($ [ox]) ? ($ [ox]) * ($ [ox])) ? ($ [I] m ($ [am]) n ($ [an]) x ($ [ox]) ? ($ [am an ox]) * ($ [I am an ox] m ($ [am]) ...) * ($ [I am an ox] I ... ... </pre> <p>And here is a sample python program:</p> <pre> import sys def addWord(root, word): add(root, word, word, '') def add(root, word, tail, prev): if tail == '': addLeaf(root, word) else: head = tail[0] tail2 = tail[1:] add(addEdge(root, head), word, tail2, head) add(addEdge(root, '?'), word, tail2, head) if prev != '*': for l in range(len(tail)+1): add(addEdge(root, '*'), word, tail[l:], '*') def addEdge(root, char): if not root.has_key(char): root[char] = {} return root[char] def addLeaf(root, word): if not root.has_key('$'): root['$'] = [] leaf = root['$'] if word not in leaf: leaf.append(word) def findWord(root, pattern): prev = '' for p in pattern: if p == '*' and prev == '*': continue prev = p if not root.has_key(p): return [] root = root[p] if not root.has_key('$'): return [] return root['$'] def run(): print("Enter words, one per line terminate with a . on a line") root = {} while 1: line = sys.stdin.readline()[:-1] if line == '.': break addWord(root, line) print(repr(root)) print("Now enter search patterns. Do not use multiple sequential '*'s") while 1: line = sys.stdin.readline()[:-1] if line == '.': break print(findWord(root, line)) run() </pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload