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?