Skip to content

Instantly share code, notes, and snippets.

@kunigami
Last active November 9, 2019 18:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kunigami/99f1e52839e74228c19d3bd3fa411513 to your computer and use it in GitHub Desktop.
Save kunigami/99f1e52839e74228c19d3bd3fa411513 to your computer and use it in GitHub Desktop.
queue = [root]
while queue is not empty:
r = queue.pop()
for each a in symbols:
let p = ps(r)
while g(p, a) is none:
p = ps(p)
// s = r + a is not in the trie
if g(r, a) is none:
f(r, a) = p
else:
s = g(r, a)
ps(s) = g(p, a)
queue.push(s)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment