Hi,

Like other suffix data structures, suffix automaton can be applied to a trie naturally. It is obvious that the number of states and transitions are linear.

There's a natural construction algorithm. Let SAM(T) be the suffix automaton for trie T. If we add a new leaf v to trie T, whose father is u with character c. We can obtain SAM(T+v) by the almost same extend function: ~~~~~ int sa_extend (int last, char c) { int cur = sz++; st[cur].len = st[last].len + 1; int p; for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link) st[p].next[c] = cur; if (p == -1) st[cur].link = 0; else { int q = st[p].next[c]; if (st[p].len + 1 == st[q].len) st[cur].link = q; else { int clone = sz++; st[clone].len = st[p].len + 1; st[clone].next = st[q].next; st[clone].link = st[q].link; for (; p!=-1 && st[p].next[c]==q; p=st[p].link) st[p].next[c] = clone; st[q].link = st[cur].link = clone; } } return cur; } ~~~~~

However, how to analysis the time complexity of construction? The amortized analysis of the 'redirect operation' part seems can not applied to a trie.