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:↵
↵
<p>Here is an example of extend function, 'last' is the corresponding state after u added:</p>↵
↵
<pre><code>↵
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;↵
}↵
</code></pre>↵
↵
I applied this method successfully on some problems. However, how to analysise the time complexity? The amortized analysis of the 'redirect operation' part seems can not be applied to a trie at first glance. If the time complexity is actually not linear, how to hack it?
↵
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:↵
↵
<p>Here is an example of extend function, 'last' is the corresponding state after u added:</p>↵
↵
<pre><code>↵
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;↵
}↵
</code></pre>↵
↵
I applied this method successfully on some problems. However, how to analys
