Construct Suffix Automaton for a Trie
Difference between en2 and en3, changed 30 character(s)
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 analys
ise 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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English BaconLi 2016-04-19 17:19:42 30 (published)
en2 English BaconLi 2016-04-19 17:11:11 280
en1 English BaconLi 2016-04-19 17:05:30 1175 Initial revision (saved to drafts)