Suffix Automaton (SAM)

For string $s$, let $u$ and $w$ be two nonempty substrings (assume $\left|u\right|\le \left|w\right|$). They have the same $\operatorname{endpos}$ if and only if every occurrence of $u$ in $s$ occurs as a suffix of $w$.

The lemma is obvious. If $u$ and $w$ have the same $\operatorname{endpos}$, then $u$ is a suffix of $w$, and in $s$ it occurs only as a suffix of $w$. Conversely, by definition, if $u$ is a suffix of $w$ and occurs in $s$ only as a suffix of $w$, then the two substrings have the same $\operatorname{endpos}$.

Consider two nonempty substrings $u$ and $w$ (assume $\left|u\right|\le \left|w\right|$). Then either $\operatorname{endpos}(u)\cap \operatorname{endpos}(w)=\varnothing$ or $\operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)$, depending on whether $u$ is a suffix of $w$:

If the sets $\operatorname{endpos}(u)$ and $\operatorname{endpos}(w)$ have at least one common element, then since $u$ and $w$ end at the same position, $u$ is a suffix of $w$. Therefore, wherever $w$ occurs, the substring $u$ also occurs. Hence $\operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)$.

Consider an equivalence class of substrings with the same $\operatorname{endpos}$, and sort all substrings in the class by nonincreasing length. Then each substring is no longer than the preceding one, and it is also a suffix of the preceding one. In other words, for any two substrings in the same equivalence class, the shorter one is a suffix of the longer one, and the lengths of the substrings in the class are consecutive, taking every integer value in some interval.

If the equivalence class contains only one substring, the lemma is obvious. We now consider an equivalence class containing more than $1$ substring.

By Lemma 1, among any two distinct strings with the same $\operatorname{endpos}$, one must be longer and one shorter, and the shorter one is always a proper suffix of the longer one. Thus, no two strings in the equivalence class have the same length.

Let $w$ be the longest string in the equivalence class and $u$ the shortest. By Lemma 1, $u$ is a proper suffix of $w$. Now consider any suffix of $w$ whose length lies in the interval $[\left|u\right|,\left|w\right|]$. It is easy to see that this suffix is also in the same equivalence class, because it can occur in $s$ only as a suffix of $w$ (this is because the shorter suffix $u$ occurs in $s$ only as a suffix of $w$). Therefore, by Lemma 1, this suffix has the same $\operatorname{endpos}$ as $w$.

All suffix links form a tree rooted at $t_0$.

Consider any state $v\neq t_0$. The state reached by $\operatorname{link}(v)$ corresponds to a strictly shorter string (by the definition of a suffix link and Lemma 3). Therefore, by following suffix links, we always eventually reach the initial state $t_0$, which corresponds to the empty string.

The tree constructed with $\operatorname{endpos}$ sets as nodes and set inclusion as edges (that is, the $\operatorname{endpos}$ set of each child is contained in the $\operatorname{endpos}$ set of its parent) is the same as the tree constructed using suffix links $\operatorname{link}$.

By Lemma 2, the $\operatorname{endpos}$ sets of any SAM form a tree (because any two sets are either disjoint or one is a subset of the other).

Now consider any state $v\neq t_0$ and its suffix link $\operatorname{link}(v)$. From the suffix link and Lemma 2, we obtain

Note that this should be $\subsetneq$ rather than $\subseteq$, because if $\operatorname{endpos}(v)=\operatorname{endpos}(\operatorname{link}(v))$, then $v$ and $\operatorname{link}(v)$ should be merged into one node.

Given the SAM of a string $s$, we can construct the SAM of $s+c$. According to the explanation of the figures above, we only need to construct the suffix path of the newly added prefix (namely $s+c$) and compress it into the existing paths. Furthermore, as described above, every node on the new suffix path must be reachable by a transition labeled $c$ from a node on a suffix path of the original string $s$.

Before adding the new character $c$ to the original string $s$, we first consider what form its suffix path can have and how it can transition through $c$. The most general case is shown below:

In the figure, the suffix path of the original string $s$ is $p_0\rightarrow p_1\rightarrow\cdots\rightarrow p_6\rightarrow t_0$, and suffix links are shown by red arrows. Some nodes (namely $p_2\sim p_6$) already have transitions labeled $c$; because appending the same character to a sequence of consecutive suffixes again produces consecutive suffixes, the endpoints of these transitions form another suffix path $q_1\rightarrow q_2\rightarrow q_3\rightarrow t_0$. There are two observations:

• On the suffix path of the original string $s$, the nodes without a transition labeled $c$ must be the first few nodes. Once some node (the node $p_2$ in the figure) has a transition labeled $c$, every subsequent node must also have a transition labeled $c$.

  Explanation: Let $s_2=\operatorname{longest}(p_2)$. Every subsequent node corresponds to a suffix of $s_2$. Thus, if $s_2+c$ also occurs in $s$, then every suffix of $s_2$ followed by $c$ must also produce a substring of $s$, so all these nodes have transitions labeled $c$.

• Although the nodes that can reach a node $q_i$ via a transition labeled $c$ must form a contiguous segment of the suffix-link tree, this segment need not lie entirely on the suffix path from $p_0$ to the root. In particular, only some of the initial nodes in the segment corresponding to $q_1$ may not be on this suffix path. For example, the node $q_1$ in the figure corresponds to $p_1'\rightarrow p_2\rightarrow p_3$, where $p_1'$ is not on the suffix path of $p_0$.

  Explanation: Let $s_2=\operatorname{longest}(p_2)$. Then $s_2+c$ corresponds to $q_1$, but clearly $s_2+c\neq\operatorname{longest}(q_1)$ in the figure, because the latter is $\operatorname{longest}(p'_1)+c$. This shows that the strings corresponding to the part of $q_1$ cannot be obtained by taking $s_2$ and its suffixes and applying transitions. Conversely, the strings in $q_2$ must be suffixes of $s_2+c$, so after removing the final $c$ they must be suffixes of $s_2$. In other words, the nodes with transitions labeled $c$ to $q_2$ must lie on the suffix path beginning at $p_2$. This is why only some nodes in the initial segment corresponding to $q_1$ may not lie on the suffix path of $p_0$.

What changes when we add a character to the end of the original string $s$—that is, add $c$—and construct the corresponding suffix path? The answer is shown below:

Since node $q_0$ is reached from the node $p_0$ corresponding to the original string $s$ by a transition labeled $c$, it corresponds to the new string $s+c$. Thus, its suffix path $q_0\rightarrow q_1''\rightarrow q_2\rightarrow q_3\rightarrow t_0$ is the newly added suffix path. If a node $p_i$ on the old suffix path already has a transition labeled $c$, the new suffix path must also pass through the node reached by that transition, so we can directly reuse the old node. The new suffix path contains exactly one completely new node, $q_0$, which receives the transitions from the initial nodes on the old suffix path that did not have transitions labeled $c$.

Besides these obvious facts, note that the old node $q_1$ is also copied once, or equivalently split into two nodes $q'_1\rightarrow q_1''$. This is because the newly added suffix path overlaps the existing paths only partially: among the strings corresponding to the old node $q_1$, only the shorter ones (those reachable from nodes $p_2$ and $p_3$) appear on the new suffix path, while the longer ones (those reachable from node $p_1'$) do not. Therefore the new suffix path can pass through only part of node $q_1$, which must be split into two nodes to represent this situation. For the same reason, as explained above, the nodes $q_2$ and $q_3$ after $q_1$ cannot be reached by transitions from nodes not on the suffix path of $p_0$, so all strings corresponding to these nodes appear on the new suffix path and no split is needed.

In terms of what states represent in a SAM, each state is an $\operatorname{endpos}$ set. Suppose the new ending position when the string is extended is $i$. Then the new node $q_0$ has ending-position set $\{i\}$, while the split nodes $q_1'$ and $q_1''$ correspond to the sets $\operatorname{endpos}(q_1)$ and $\operatorname{endpos}(q_1)\cup\{i\}$, respectively. The later nodes $q_2$ and $q_3$ in fact also gain $i$ in their existing ending-position sets. In other words, although $q_2$, $q_3$, and their associated transitions do not change, the $\operatorname{endpos}$ sets they represent do become larger.

The above describes the most complex and general case (namely case 3 below). In practice, node $p'_1$ may not exist, so no split is needed (namely case 2 below). To determine this case, it is enough to check whether $\operatorname{longest}(q_1)=\operatorname{longest}(p_2)+c$, equivalently $\operatorname{len}(q_1)=\operatorname{len}(p_2)+1$. It is also possible that none of the nodes on the suffix path of $p_0$ has a transition labeled $c$; then only the new node $q_0$ needs to be created (namely case 1 below).

• Let $\textit{last}$ be the state corresponding to the entire string before character $c$ is added (initially, set $\textit{last}=0$; the final step of the algorithm updates $\textit{last}$).

• Create a new state $\textit{cur}$ and set $\operatorname{len}(\textit{cur})$ to $\operatorname{len}(\textit{last})+1$; at this point the value of $\operatorname{link}(\textit{cur})$ is unknown.

• Now perform the following process: starting from state $\textit{last}$, if the current state does not yet have a transition labeled $c$, add a transition labeled $c$ to state $\textit{cur}$ and move the current state along its suffix link. If we encounter a state that already has a transition labeled $c$, stop and mark this state as $p$.

• Case 1: If no such state $p$ is found, we have reached the virtual state $-1$; set $\operatorname{link}(\textit{cur})$ to $0$ and exit.

• Suppose now that we have found a state $p$ with a transition labeled $c$. Mark the state reached by this transition as $q$. Then either $\operatorname{len}(p)+1=\operatorname{len}(q)$ or $\operatorname{len}(p)+1<\operatorname{len}(q)$.

• Case 2: If $\operatorname{len}(p)+1=\operatorname{len}(q)$, simply set $\operatorname{link}(\textit{cur})$ to $q$ and exit.

• Case 3: Otherwise, the situation is more complicated and we need to clone state $q$: create a new state $\textit{clone}$, copying all information from $q$ except its $\operatorname{len}$ value (including its suffix link and transitions). Set $\operatorname{len}(\textit{clone})$ to $\operatorname{len}(p)+1$.

  After cloning, set the suffix link from $\textit{cur}$ to $\textit{clone}$, and also set the suffix link from $q$ to $\textit{clone}$.

  Finally, walk back along suffix links from state $p$. Whenever a visited state has a transition to state $q$, reconnect that transition to state $\textit{clone}$.

• After handling all three cases above, update $\textit{last}$ to state $\textit{cur}$.

• If a transition $(p,q)$ satisfies $\operatorname{len}(p)+1=\operatorname{len}(q)$, we call it a continuous transition. Otherwise, when $\operatorname{len}(p)+1<\operatorname{len}(q)$, it is called a non-continuous transition.

  As can be seen from the algorithm description, continuous and non-continuous transitions are handled differently. Continuous transitions are fixed; we never change them again. In contrast, when a new character is inserted into the string, a non-continuous transition may change (the endpoint of the transition edge may change).

• To avoid ambiguity, before the current character $c$ is inserted into the SAM, denote the string by $s$.

• The algorithm starts by creating a new state $\textit{cur}$ corresponding to the entire string $s+c$. The reason for creating a new node is clear. At the same time, we also create a new character and a new equivalence class.

• After creating a new state, we move from the state corresponding to the entire string $s$, namely $\textit{last}$, along suffix links. For every state visited, we try to add a transition labeled $c$ to the new state $\textit{cur}$.

  However, we can add only transitions that do not conflict with existing transitions. Therefore, as soon as we find an existing transition labeled $c$, we must stop.

• The simplest case is that we reach the virtual state $-1$, which means that every suffix of $s$ has received a transition labeled $c$. This also means that character $c$ has never appeared in $s$. Therefore, the suffix link of $\textit{cur}$ is state $0$.

• In the second case, we find an existing transition $(p,q)$. This means that we are trying to add to the automaton a string $x+c$ that already exists (where $x$ is a suffix of $s$, and the string $x+c$ has already appeared as a substring of $s$). Since we assume that the construction of the automaton for $s$ is correct, we should not add a new transition here.

  The difficulty, however, is determining which state the suffix link from $\textit{cur}$ should point to. We need to link it to a state whose longest corresponding string is exactly $x+c$, so that the state's $\operatorname{len}$ should be $\operatorname{len}(p)+1$. Such a state may not exist, namely when $\operatorname{len}(q)>\operatorname{len}(p)+1$. In that case, we must split state $q$ to create such a state.

• Of course, if transition $(p,\,q)$ is continuous, then $\operatorname{len}(q)=\operatorname{len}(p)+1$. In this case everything is simple: we only need to make the suffix link of $\textit{cur}$ point to state $q$.

• Otherwise, the transition is non-continuous, namely $\operatorname{len}(q)>\operatorname{len}(p)+1$. This means that state $q$ corresponds not only to the suffix $s+c$ of length $\operatorname{len}(p)+1$, but also to longer substrings of $s$. We have no choice but to split state $q$ into two substates, so the length of the first substate is $\operatorname{len}(p)+1$.

  How do we split a state? We clone state $q$, producing a state $\textit{clone}$, and set $\operatorname{len}(\textit{clone})$ to $\operatorname{len}(p)+1$. Since we do not want to change paths passing through $q$, we copy all transitions of $q$ to $\textit{clone}$. We also set the suffix link from $\textit{clone}$ to the target of $q$'s suffix link, and set the suffix link of $q$ to $\textit{clone}$.

  After splitting the state, set the suffix link from $\textit{cur}$ to $\textit{clone}$.

  In the final step, we reconnect some transitions that originally pointed to $q$ to $\textit{clone}$. Which transitions need to be modified? It is enough to reconnect exactly the suffixes of all strings $w+c$, where $w$ is the longest string corresponding to state $p$. In other words, we continue moving along suffix links from node $p$ until reaching the virtual state $-1$, or until the current state's transition labeled $c$ no longer points to state $q$.

If we consider the different parts of the algorithm, there are three places whose time complexity is not obviously linear:

• The first is traversing all suffix links of $\textit{last}$ and adding transitions labeled $c$.
• The second is copying transitions when state $q$ is copied to a new state $\textit{clone}$.
• The third is modifying transitions pointing to $q$ and reconnecting them to $\textit{clone}$.

We use the fact that the size of a SAM (the number of states and transitions) is linear (the proof that the number of states is linear is the algorithm itself; the proof that the number of transitions is linear is given after the implementation).

Therefore, the total complexity of the first and second parts above is clearly linear, because each operation adds only one new transition to the automaton in amortized terms.

We still need to estimate the total complexity of the third part, in which transitions initially pointing to $q$ are reconnected to $\textit{clone}$. Let $v=\operatorname{longest}(p)$, which is a suffix of $s$. On each iteration, the length of $v$ decreases, so the starting position of $v$ as a suffix of $s$ necessarily moves to the right. Therefore, the number of times that $p$ moves along suffix links in the loop is no more than the distance by which the starting position of $v$ as a suffix of $s$ moves to the right. Since $p$ must move at least once to terminate the loop, and since $p$ is at least the result of moving $last$ once along a suffix link, when the loop terminates the starting position of $v$ as a suffix of $s$ is no earlier than that of $\operatorname{longest}(\operatorname{link}(\operatorname{link}(\textit{last}))$. Moreover, when the loop terminates, the starting position of $v$ as a suffix of $s$ is exactly the starting position of $v+c$ as a suffix of $s+c$; as a suffix of $s+c$, the string $v+c$ is exactly $\operatorname{longest}(\operatorname{link}(\operatorname{link}(\textit{cur}))$. Since $cur$ is the updated value of $last$, the number of moves in the loop is no more than the distance by which $\operatorname{longest}(\operatorname{link}(\operatorname{link}(\textit{last}))$ moves to the right as a suffix of the current string between its old and new values, plus one (the move needed to terminate the loop).

Because the position of the string $\operatorname{longest}(\operatorname{link}(\operatorname{link}(\textit{last}))$ as a suffix of the current string increases monotonically throughout the entire SAM construction³, its total movement is at most $n$. This shows that the number of iterations in the loop modifying transitions pointing to $q$ is at most $2n$. This is exactly what we needed to prove.

void sam_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  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;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

The algorithm itself proves this claim. At the beginning the automaton contains one state; the first and second iterations create only one node each, and each of the remaining $n-2$ steps creates at most $2$ states.

We can also prove this bound without using the algorithm. Recall that the number of states equals the number of distinct $\operatorname{endpos}$ sets. These $\operatorname{endpos}$ sets form a tree (the $\operatorname{endpos}$ set of a parent contains the $\operatorname{endpos}$ set of a child). Consider slightly modifying this tree: whenever it has an internal node with only one child (which means that the child's set omits at least one position from the parent's set), create a child whose set contains those omitted positions. In the end, we obtain a tree in which every internal node has degree greater than one, and the number of leaves is at most $n$. Such a tree has at most $2n-1$ nodes, so the number of distinct $\operatorname{endpos}$ sets in the original tree is also at most $2n-1$.

The string $\mathtt{abbb} \cdots \mathtt{bbb}$ reaches this upper bound: from the third iteration onward, every iteration splits a state, ultimately producing exactly $2n-1$ states.

We first estimate the number of continuous transitions. Consider the spanning tree formed by the longest paths from state $t_0$ to all states in the automaton. The spanning tree contains only continuous edges, so its number of edges is less than the number of states, and hence no more than $2n-2$.

We now estimate the number of non-continuous transitions. Let the current non-continuous transition be $(p,\,q)$, with character $c$. Consider its corresponding string $u+c+w$, where $u$ corresponds to a longest path from the initial state to $p$, and $w$ corresponds to a longest path from $q$ to any terminal state. On the one hand, the strings of the form $u+c+w$ corresponding to different non-continuous transitions are distinct (because $u$ and $w$ consist only of continuous transitions). On the other hand, by the definition of terminal states, every string of the form $u+c+w$ is a suffix of the whole string $s$. Since $s$ has $n$ nonempty suffixes, and none of the strings of the form $u+c+w$ is $s$ itself (because the whole string consists only of continuous transitions), the total number of non-continuous transitions is at most $n-1$.

Adding the two estimates above gives the upper bound $3n-3$. However, the maximum number of states can occur only in cases like $\mathtt{abbb} \cdots \mathtt{bbb}$, and in that case the number of transitions is clearly less than $3n-3$.

Therefore we obtain the tighter upper bound $3n-4$ for the number of SAM transitions. The string $\mathtt{abbb} \cdots \mathtt{bbbc}$ reaches this bound.

In time $O(\left|T\right|)$, we construct a suffix automaton for the text string $T$. To check whether a pattern string $P$ occurs in $T$, we start at $t_0$ and follow transitions according to the characters of $P$. If at some point no transition is available, then $P$ is not a substring of $T$. If we process the entire string $P$ this way, then the pattern occurs in $T$.

For each string $P$, the time complexity of the algorithm is $O(\left|P\right|)$. In addition, this algorithm finds the maximum prefix length of $P$ that occurs in the text string.

Construct a suffix automaton for the string $S$.

Every substring of $S$ corresponds to some path in the automaton. Therefore, the number of distinct substrings equals the number of distinct paths starting at $t_0$ in the automaton.

Since the SAM is a directed acyclic graph, the number of paths can be computed by dynamic programming. Let $d_{v}$ be the number of paths starting from state $v$ (including the path of length zero). Then we have the recurrence:

That is, $d_{v}$ is the sum over the endpoints of all transitions from $v$; the triple $(v,w,c)$ in $DAWG$ means that the suffix automaton has a transition from $v$ to $w$ via $c$.

Thus, the number of distinct substrings is $d_{t_0}-1$ (because the empty substring must be removed).

The total time complexity is $O(\left|S\right|)$.

Another method is to use the information in the suffix-link tree after constructing the suffix automaton. The number of substrings corresponding to each node is $\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v))$; summing this over all automaton nodes gives the answer.

The total time complexity is still $O(\left|S\right|)$.

The solution to this problem is similar to that of the previous problem, except that we now need to perform dynamic programming in two parts: the number $d_{v}$ of distinct substrings and their total length $ans_{v}$.

We introduced how to calculate $d_{v}$ in the previous problem. The value of $ans_{v}$ can be calculated by the following recurrence:

We take the answer for each adjacent node $w$ and add $d_{w}$, because every substring starting from state $v$ gains one character.

The time complexity of the algorithm is still $O(\left|S\right|)$.

We can likewise use information from the suffix-link tree. The total lengths of all suffixes of the longest substring corresponding to each node are

and subtracting the corresponding value for its $\operatorname{link}$ node gives the net contribution of that node. Summing over all nodes of the automaton is sufficient.

The total time complexity is still $O(\left|S\right|)$.

The idea for solving this problem can be developed from the ideas used for the first two problems. The $k$-th largest substring in lexicographic order corresponds to the $k$-th largest path in the SAM. Therefore, after calculating the number of paths from each state, we can easily find the $k$-th largest path starting from the root of the SAM.

The preprocessing time complexity is $O(\left|S\right|)$, and the complexity of a single query is $O(\left|ans\right|\cdot\left|\Sigma\right|)$, where $ans$ is the query answer and $\left|\Sigma\right|$ is the size of the character set.

It is easy to see that $S+S$ contains all cyclic shifts of $S$ as substrings.

Thus the problem reduces to finding, in the suffix automaton of $S+S$, the smallest path of length $\left|S\right|$. This can be done trivially: starting from the initial state, greedily follow the smallest character.

The total time complexity is $O(\left|S\right|)$.

Using information from the suffix-link tree, we can preprocess the size of the $\operatorname{endpos}$ set of every node with a DFS.

Initialize the set size of every “prefix node” to $1$, and that of every non-“prefix node” to $0$. Then, while traversing upward along suffix links from the bottom, add the set sizes of all child nodes to each parent node (do not omit the parent's own initial value). The resulting value at each node is the size of its $\operatorname{endpos}$ set. The reason the set sizes of different child nodes can be added directly is that the same $v_i$ appears in only one subtree, so the addition does not duplicate anything.

During a query, find the node corresponding to the pattern string $P$ in the automaton. If it exists, the answer is the size of that node's $\operatorname{endpos}$ set; otherwise, the answer is $0$.

The preprocessing time complexity is $O(|T|)$, and the time complexity of a single query is $O(|P|)$.

Construct a suffix automaton for the text string $T$.

Then preprocess, for every state $v$ in the automaton, a value $cnt_{v}$ equal to the size of the $\operatorname{endpos}(v)$ set. In fact, all substrings corresponding to the same state $v$ occur the same number of times in the text string $T$; this is the number of positions in the $\operatorname{endpos}$ set.

However, we cannot explicitly construct the $\operatorname{endpos}$ sets, so we only consider their sizes $cnt$.

To calculate these values, perform the following operations. For each state, if it was not created by copying (and is not the initial state $t_0$), initialize its $cnt$ to 1. Then traverse all states in decreasing order of their length $\operatorname{len}$ and add the current value of $cnt_{v}$ to the state pointed to by its suffix link:

After this, the answer for every state is correct.

Why is this correct? There are exactly $\left|T\right|$ states that were not obtained by copying, and the first $i$ of them were created when the first $i$ characters were inserted. Thus, for each such state, when it is processed, we count the number of positions corresponding to it. We therefore initially set the $cnt$ of these states to $1$ and the $cnt$ of all other states to $0$.

Next, for each $v$, perform the following operation: $cnt_{\operatorname{link}(v)}+=cnt_{v}$. Its meaning is that if a string $v$ occurs $cnt_{v}$ times, all of its suffixes end at exactly the same positions, and therefore also occur $cnt_{v}$ times.

Why do we not count any position more than once in this process? Because we add the positions of one state to only one other state, so a state cannot point its positions to another state in two different ways.

Therefore, in $O(\left|T\right|)$ time, all state values $cnt$ can be calculated.

Finally, answering a query only requires looking up $cnt_{t}$, where $t$ is the state corresponding to the pattern string. If the pattern string does not exist, the answer is $0$. The time complexity of a single query is $O(\left|P\right|)$.

Using information from the suffix-link tree, we can preprocess the minimum value in the $\operatorname{endpos}$ set of every node with a DFS.

Initialize every “prefix node” $v_i$ to $i$, and every non-“prefix node” to $\infty$. Then, while traversing upward along suffix links from the bottom, compare each parent's value with the values of all its child nodes and take the minimum (do not omit the parent's own initial value). The resulting value at each node is the minimum value in its $\operatorname{endpos}$ set.

During a query, find the node corresponding to the pattern string $P$ in the automaton. If it exists, the answer is its value minus $|P|-1$; otherwise, the answer does not exist.

The preprocessing time complexity is $O(|T|)$, and the time complexity of a single query is $O(|P|)$.

Construct a suffix automaton. For every state in the SAM, preprocess the position $\operatorname{firstpos}$. That is, for each state $v$, find the position where a string represented by this state first occurs, $\operatorname{firstpos}[v]$. In other words, find the minimum element of each $\operatorname{endpos}$ set (although we obviously cannot maintain all $\operatorname{endpos}$ sets explicitly).

To maintain these $\operatorname{firstpos}$ positions, extend the function sam_extend(). When creating a new state $\textit{cur}$, set

When copying node $q$ to $\textit{clone}$, set

(The only other possible value, $\operatorname{firstpos}(\textit{cur})$, is clearly too large.)

The answer to a query is then $\operatorname{firstpos}(t)-\left|P\right|+1$, where $t$ is the state corresponding to the string $P$. A single query takes only $O(\left|P\right|)$ time.

After finding the node corresponding to the pattern string $P$, traverse its subtree using information from the suffix-link tree, and output a position whenever a terminal node is found.

The complexity of a single query is $O(|P|)+O(\textit{answer}(P))$, where $\textit{answer}(P)$ is the answer to the query. As in the proof that the number of states is linear, the size of a subtree in the suffix-link tree is no more than twice the size of that node's $\operatorname{endpos}$ set, so the subtree traversal has complexity $O(\textit{answer}(P))$.

Again, construct a suffix automaton for the text string $T$. As in the previous problem, calculate $\operatorname{firstpos}$ for every state.

If $t$ is the state corresponding to the pattern string $P$, then $\operatorname{firstpos}(t)$ is clearly one of the answers. We have already found the state corresponding to $P$ in the automaton. Which other positions do we need to find? They are precisely those corresponding to strings that have $P$ as a suffix. In other words, we need to find all states from which state $t$ can be reached by suffix links.

Therefore, to solve this problem, we need to store, for each state, a list of suffix links pointing to it. The query answer consists, for every state found by performing DFS or BFS from state $t$ using only reversed suffix links, of its $\operatorname{firstpos}$ value.

The preprocessing complexity is $O(|T|)$, and the complexity of a single query is $O(|P|+\textit{answer}(P))$.

We never visit a state more than once, because each state has only one suffix link, so there cannot be two different paths to the same state.

We only need to consider different states that may have the same $\operatorname{firstpos}$ value. This happens only when one state is copied from another. However, this does not affect the complexity analysis. As in the proof that the number of states is linear, the number of such states whose suffix is $P$ is no more than $2\textit{answer}(P)$.

Moreover, we can remove duplicate positions by ignoring the $\operatorname{firstpos}$ values of copied nodes. In fact, for a state, if it can be reached through the copied state, it can also be reached through the original state. Thus, if we record a marker is_clone for each state to indicate whether it was copied, we can simply ignore copied states and output the $firstpos$ values of all other states.

The following is a rough implementation:

struct state {
  bool is_clone;
  int first_pos;
  std::vector<int> inv_link;
  // some other variables
};

// After constructing the SAM
for (int v = 1; v < sz; v++) st[st[v].link].inv_link.push_back(v);

// Output all occurrence positions
void output_all_occurrences(int v, int P_length) {
  if (!st[v].is_clone) cout << st[v].first_pos - P_length + 1 << endl;
  for (int u : st[v].inv_link) output_all_occurrences(u, P_length);
}

Perform dynamic programming on the suffix automaton of string $S$.

Suppose that we have already processed part of the substring and are currently at state $v$. Let the minimum number of characters that must be added at state $v$ to obtain a transition that does not occur be $d_v$.

Computing $d_{v}$ is simple. If there is no transition using at least one character from the character set, then $d_{v}=1$. Otherwise, adding one character is not enough, and we take the minimum over all transitions:

The answer is $d_{t_0}$, and the string can be reconstructed backward using the computed array $d$.

Construct a suffix automaton for string $S$.

We now process string $T$. For every prefix, find the longest suffix of that prefix that occurs in $S$. In other words, for every position in $T$, find the length of the longest common substring of $S$ and $T$ ending at that position.

To do this, use two variables, current state $v$ and current length $l$. They describe the currently matched part: its length and the state corresponding to it.

Initially, $v=t_0$ and $l=0$, meaning that the match is the empty string.

We now describe how to add a character $T_{i}$ and recompute the answer:

• If there is a transition from $v$ using character $T_{i}$, simply follow it and increment $l$.

• If no such transition exists, shorten the current match, which means following a suffix link:

  $$v=\operatorname{link}(v)$$

  At the same time, shorten the current length. We clearly need to set $l$ to $\operatorname{len}(v)$, because the longest string corresponding to the state reached through this suffix link is a substring.

• If there is still no transition using this character, continue following suffix links and decreasing $l$ until a transition is found or the virtual state $-1$ is reached. The latter means that character $T_{i}$ does not occur in $S$ at all, so set $v=l=0$.

Clearly, the answer is the maximum of all values of $l$.

The time complexity of this part is $O(\left|T\right|)$, because each move either increases $l$ by one or moves along suffix links several times, decreasing $l$ on each move.

Code:

string lcs(const string &S, const string &T) {
  sam_init();
  for (int i = 0; i < S.size(); i++) sam_extend(S[i]);

  int v = 0, l = 0, best = 0, bestpos = 0;
  for (int i = 0; i < T.size(); i++) {
    while (v && !st[v].next.count(T[i])) {
      v = st[v].link;
      l = st[v].length;
    }
    if (st[v].next.count(T[i])) {
      v = st[v].next[T[i]];
      l++;
    }
    if (l > best) {
      best = l;
      bestpos = i;
    }
  }
  return T.substr(bestpos - best + 1, best);
}

Concatenate all the substrings into one longer string $T$, separating each string with a special character $D_i$ (one character for each string):

Then construct a suffix automaton for string $T$.

We now need to find, in the automaton, a string that occurs in every string $S_i$. The added special characters are useful here. If $S_j$ contains a substring $X$, then from the node corresponding to substring $X$, denoted $t$, there must be a path to $D_j$ that passes through none of the other special characters $D_1,\cdots,D_{j-1},D_{j+1},\cdots,D_k$. For a common substring $X$, such a path must exist for every special character $D_j$.