Suffix Automaton

A suffix automaton is a compact directed acyclic graph representing all substrings of a text. Reading a substring from the initial state follows character-labeled transitions; if the path exists, that substring occurs. The same structure can count distinct substrings without enumerating them, and can be extended to count occurrences or find common substrings of two texts. It is built online, one appended character at a time. Understanding its states requires a stronger idea than a trie: several substrings may share a state when they have exactly the same set of ending positions. Our fixed-lowercase implementation builds the automaton, counts distinct nonempty substrings, and answers substring-membership queries.

Prerequisites: Tries, directed graphs, string suffixes, equivalence classes; comfort with invariants and amortized complexity.

Build the idea

1. 1. Group by ending positions

   For a substring x, endpos(x) is the set of text positions where an occurrence of x ends. In abb, b ends at positions 1 and 2, while ab ends only at 1. Substrings with identical endpos sets form one state. Every noninitial state v represents a consecutive interval of substring lengths: len[link[v]]+1 through len[v]. len[v] is the longest represented length. link[v] points to the state containing the longest proper suffix of a representative whose ending-position set is different. A suffix link removes characters; a transition appends one character. They are not interchangeable edges.

2. 2. Append one character

   Keep last, the state of the entire processed text. Appending c creates cur with len[cur]=len[last]+1. Starting from last, walk suffix links and add a c-transition to cur wherever one is missing. These states correspond to suffixes that gain a new continuation at this position. If the walk reaches -1, link cur to the initial state. Otherwise it reaches p with an existing c-transition to q. We must decide whether q can be reused unchanged or whether its previous equivalence class must be divided.

3. 3. The simple existing-transition case

   If len[p]+1 equals len[q], q is already the correct suffix-link target for cur. The new ending occurrence adds no need to separate short and long representatives in q. Set link[cur]=q. If len[p]+1 is smaller than len[q], however, the transition now needs a state whose longest represented substring has that shorter length. Reusing q as-is would incorrectly merge substrings that no longer have equal ending-position sets. That is the reason for cloning, rather than a mysterious extra optimization.

4. 4. Split a state with a clone

   Create clone as a copy of q's transitions and suffix link, but set len[clone]=len[p]+1. Along suffix links from p, redirect exactly those c-transitions that still lead to q, sending them to clone. Finally set link[q]=link[cur]=clone. The clone preserves previously possible continuations while separating the shorter representatives from q's longer ones. It is a structural state, not a newly read text position. If occurrence counts are added later, clone must start with zero direct terminal-occurrence contribution; blindly copying q's occurrence count would overcount.

5. 5. Trace an actual clone in abb

   After ab, the state for ab also represents b: both currently end only at position 1. Appending the second b creates the state for abb and adds its missing b-transition from the previous last state. Walking back reaches the initial state, whose b-transition points to the old ab state q. Here len[root]+1=1 but len[q]=2, so clone q with length 1. The clone now represents b, which ends at positions 1 and 2; q represents ab, ending only at 1. The new last state represents bb and abb, both ending at 2. The five distinct substrings are a,b,ab,bb,abb.

6. 6. Count substrings using length intervals

   For each state v other than the initial state, there is exactly one represented substring of each length in its interval. They are the suffixes of its longest representative with lengths len[link[v]]+1 through len[v]. Therefore v contributes len[v]-len[link[v]] distinct substrings. Sum these contributions in long long. States partition all nonempty substrings by endpos equivalence, so no substring is missed or counted twice. The clone step adjusts interval boundaries through changed suffix links, making the same formula remain valid after every extension.

7. 7. Membership, bounds, and limitations

   Start a membership query at state 0 and follow one transition per pattern character; a missing transition means NO. Any reachable path spells an occurring substring, so no terminal marking is needed for this query. Terminal marking would instead distinguish whole suffixes. The empty pattern is accepted as a substring, but the distinct count deliberately excludes it. At most one ordinary state and one clone are created per appended character, giving at most 2n states for n>0 and one state for empty text. We store 26 transitions per state, so alphabet restrictions are real, not cosmetic. General Unicode requires a different symbol model.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<array>
#include<limits>
using namespace std;
struct State{
    int len=0,link=-1;
    array<int,26>next;
    State(){
        next.fill(-1);
    }
};
struct SuffixAutomaton{
    vector<State>st=vector<State>(1);
    int last=0;
    void extend(char ch){
        int c=ch-'a',cur=(int)st.size();
        st.emplace_back();
        st[cur].len=st[last].len+1;
        int p=last;
        // Every missing continuation gains the newly appended occurrence.
        while(p!=-1&&st[p].next[c]==-1){
            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{
                State copy=st[q]; // Copy before push_back can reallocate.
                int clone=(int)st.size();
                st.push_back(copy);
                st[clone].len=st[p].len+1;
                // Split the old class: only transitions still targeting q change.
                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;
    }
    long long distinct()const{
        long long answer=0;
        // Each state's consecutive length interval contributes once.
        for(int v=1;v<(int)st.size();v++){
            answer+=st[v].len-st[st[v].link].len;
        }
        return answer;
    }
    bool contains(const string&pattern)const{
        int v=0;
        for(char c:pattern){
            v=st[v].next[c-'a'];
            if(v==-1){
                return false;
            }
        }
        return true; // Empty pattern follows an empty path.
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s);
    SuffixAutomaton sam;
    for(char c:s){
        sam.extend(c);
    }
    cout<<sam.distinct()<<'\n';
    int q;
    cin>>q;
    cin.ignore(numeric_limits<streamsize>::max(),'\n');
    while(q--){
        string pattern;
        getline(cin,pattern);
        cout<<(sam.contains(pattern)?"YES":"NO")<<'\n';
    }
}

Complexity analysis

With fixed alphabet size 26, construction is O(n) amortized time and O(26n)=O(n) space; suffix-link walks and transition redirections have a linear aggregate bound. One extension can take longer than constant time. Counting distinct substrings takes O(n); a query of length m takes O(m). For n>2, sharper bounds are 2n−2 states and 3n−4 actual transition edges; the dense storage still reserves 26 slots per state.

Example input and output

First line: lowercase text, possibly empty, length≤200000. Then q on its own line and q pattern lines, each lowercase and possibly empty. Print the number of distinct nonempty text substrings, then YES/NO for each pattern. Empty pattern always receives YES. Inputs must respect the lowercase alphabet.

Input

abb
4
ab
bb
ba

Output

5
YES
YES
NO
YES

The distinct nonempty substrings are a,b,ab,bb,abb. ab and bb occur, ba does not, and the final blank pattern occurs by the empty-substring convention.

Practical applications

Online distinct-substring counts; substring membership; occurrence counting after suffix-link aggregation; longest common substring. Foundational reference: Blumer et al., The smallest automaton recognizing the subwords of a text.

Check your understanding

Why is a clone created when len[p]+1<len[q]?

Put it into practice

After each character of the text, print the current number of distinct nonempty substrings.