Hi,
Like some 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 add v) by the almost same extend function:
Here is an example of extend function, 'last' is the corresponding state after u added:
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;
}
I applied this method successfully on some problems. However, how to analyse the time complexity? The amortized analysis of the 'redirect operation' can not be applied to a trie at first glance. If the time complexity is actually not linear, how to hack it?