SyntaxPilot
Courses/Competitive Programming/Lesson 78
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 78 of 90

Suffix automaton basics

queued

These are the notes for Competitive Programming episode 78. The suffix automaton (SAM) of a text is the smallest machine that reads a word letter by letter and accepts exactly the substrings of the text. It has at most 2n − 1 states and 3n − 4 edges, and it is built online, one letter at a time, with extend(c). A state is a class of substrings with the same end positions (endpos); each state stores len (its longest string) and a suffix link. Snippet Check (is each query a substring?) shows find per query (TLE on 10^5 queries) and a real bug: without redirecting the edges to the clone, ala is reported missing from masalachai. Distinct Snippets, again counts the different substrings as Σ len(v) − len(link(v)), and gets exactly episode 77's answer, 19999478579. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Picture a city's bus map with a separate stop for every journey anyone ever started: it explodes (that's a trie of all suffixes). A smart planner notices that two stops with exactly the same onward routes can be one stop: nobody can tell them apart by where they go next (a state = substrings with the same future). Each stop has a sign to a shorter journey, the same trip with its first part dropped, which can go to more places (the suffix link). And when the city adds a new road at the end, only the stops along those signs get a new bus (extend(c)); the rest of the map stays.

Problem M1 · Snippet Check

(Written for this course.)

  • A text t (|t| ≤ 2·10^5) and q ≤ 10^5 query words (total length ≤ 2·10^5), all lowercase.
  • For each query print YES if it is a substring (a continuous piece) of t, else NO.
masalachai 5
chai
masa
ala
lachai
chaimasala

masalachai contains chai, masa, ala and lachai, but not chaimasala.

Attempt 1: find for every query (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t;
    int q;
    cin >> t >> q;
    while (q--) {
        string p;
        cin >> p;
        cout << (t.find(p) != string::npos ? "YES" : "NO") << "\n";
    }
}
YES
YES
YES
YES
NO

Correct, but with t = 200000 a's and 100000 queries ab, every find tries every position of the text before giving up: q · |t| = 2·10^10 steps. The SyntaxPilot compiler stops it with Time Limit Exceeded:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    string t(200000, 'a');                        // 200000 a's
    int q = 100000;                                 // 100000 queries of "ab"
    int yes = 0;
    while (q--) {
        string p = "ab";
        if (t.find(p) != string::npos) yes++;       // scans the whole text
    }
    cout << yes << " YES\n";
}

Why not a trie of every suffix?

Every substring is the start of a suffix, so a trie of all suffixes answers a query in |p| steps. But a random text has almost all its n(n+1)/2 substrings different, so the trie has about n²/2 ≈ 2·10^10 nodes. Most of those nodes have exactly the same future, so we merge them.

End positions (endpos)

  • endpos(x) = the set of positions where an occurrence of x ends.
  • In banana (0-based): endpos(na) = endpos(ana) = {3, 5}, endpos(a) = {1, 3, 5}, endpos(nana) = endpos(anana) = endpos(banana) = {5}.
  • Same endpos ⇒ the same letters can follow ⇒ the same state.
  • The strings of one state are suffixes of each other with consecutive lengths len(link(v)) + 1 … len(v); the state stores only len(v).
  • The suffix link of v points to the state of the longest suffix of v's strings that is in a different state (it ends in more places).
  • Theorem: at most 2n − 1 states and 3n − 4 edges (n ≥ 3).

extend(c): add one letter

  1. cur = a new state with len = len(last) + 1 (the whole text so far).
  2. Walk p = last, link(last), … and while p has no edge c, add p —c→ cur.
  3. If the walk fell off the root (p = −1): link(cur) = 0.
  4. Otherwise let q = p —c→. If len(p) + 1 == len(q): link(cur) = q.
  5. Otherwise clone q: a copy with len = len(p) + 1, q's edges and q's link. Redirect every p —c→ q on the walk to the clone, then link(q) = link(cur) = clone.

Amortised O(1) state changes per letter (plus copying 26 edges for each clone).

Example: abb. After a and ab the states are a chain 0 → 1 (a) → 2 (ab). Adding the last b: state 3 = abb; the walk adds 2 —b→ 3, then reaches the start, whose b edge goes to state 2 = {ab, b}. But now b ends at positions {1, 2} while ab ends only at {1}, so the state splits: the clone 4 = {b} with len 1. The start's b edge is redirected to 4, and link(2) = link(3) = 4, link(4) = 0.

state strings len link
0 (empty) 0 −1
1 a 1 0
2 ab 2 4
3 abb, bb 3 4
4 (clone) b 1 0

The missing redirect bug

The automaton without the redirect loop in the clone step:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t;
    int q;
    cin >> t >> q;
    SuffixAutomaton sam;
    for (char ch : t) sam.extend(ch);
    while (q--) {
        string p;
        cin >> p;
        cout << (sam.contains(p) ? "YES" : "NO") << "\n";
    }
}
YES
YES
NO
YES
NO

ala is in masalachai, but an edge still points to the old state q, which lost the strings that moved to the clone: the walk takes a wrong turn.

The fix: redirect the edges to the clone

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t;
    int q;
    cin >> t >> q;
    SuffixAutomaton sam;
    for (char ch : t) sam.extend(ch);
    while (q--) {
        string p;
        cin >> p;
        cout << (sam.contains(p) ? "YES" : "NO") << "\n";
    }
}
YES
YES
YES
YES
NO

Edge case: a one-letter text.

a 2
a
aa
YES
NO

The worst case that killed find (two steps per query):

0 YES, 200001 states

Problem M2 · Distinct Snippets, again

(Episode 77's problem.) Count the different non-empty substrings of s, |s| ≤ 2·10^5.

Observation. Every substring has exactly one endpos set, so it lives in exactly one state, and state v holds one substring of each length len(link(v)) + 1 … len(v), i.e. len(v) − len(link(v)) substrings. Sum over all states except the start.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    SuffixAutomaton sam;
    for (char ch : s) sam.extend(ch);
    ll total = 0;
    for (int v = 1; v < (int)sam.st.size(); v++)    // each state: lengths link.len+1 .. len
        total += sam.st[v].len - sam.st[sam.st[v].link].len;
    cout << total << " (" << sam.st.size() << " states)\n";
}
15 (10 states)

The same 200000 random letters as episode 77 (mt19937 gen(77)):

19999478579 (251796 states)

Exactly the suffix array's answer, with 251796 states (< 2n).

Stress test

Both problems against brute force (a set of every substring, and find) on 500 random strings:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {
    mt19937 gen(78);
    for (int it = 1; it <= 500; it++) {
        string s(gen() % 12 + 1, 'a');
        for (char& c : s) c = 'a' + gen() % 3;
        set<string> all;                            // brute force: every substring
        for (int i = 0; i < (int)s.size(); i++)
            for (int len = 1; i + len <= (int)s.size(); len++) all.insert(s.substr(i, len));
        SuffixAutomaton sam;
        for (char ch : s) sam.extend(ch);
        ll fast = 0;
        for (int v = 1; v < (int)sam.st.size(); v++) fast += sam.st[v].len - sam.st[sam.st[v].link].len;
        string p(gen() % 4 + 1, 'a');
        for (char& c : p) c = 'a' + gen() % 3;
        bool slow = s.find(p) != string::npos;
        if ((ll)all.size() != fast || slow != sam.contains(p)) { cout << "mismatch on " << s; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Memory Verdict
find per query O(q · t ) ≈ 2·10^10
trie of every suffix O(n²) O(n²) nodes out of memory
build the suffix automaton O(26 · n) ≤ 2n states fast
M1 queries O(Σ p )
M2 distinct substrings O(n) — accepted

Memory: 28 ints per state (len, link, 26 edges), about 45 MB for 4·10^5 states. With a big alphabet, store the edges in a map<char,int> instead.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
no redirect after the clone ala → NO old edges skip the clone while (p != -1 && next[p][c] == q) next[p][c] = clone, p = link[p];
clone without q's edges or link Wrong Answer the clone is a full copy, only shorter {len(p) + 1, link(q), next(q)}
room for only n states Runtime Error clones add up to n − 1 more up to 2n states
counting the start state garbage or Runtime Error its link is −1, so it reads st[−1] (and it is the empty string) sum from v = 1
int for the distinct count overflow up to 2·10^10 long long
push_back while holding a reference State& s = st[q] Runtime Error / garbage the vector reallocates use indices, copy before pushing

Mini project

Autocomplete check for a chat app. Build the SAM of a long chat log once. For each word the user types, walk the automaton letter by letter and show, after every letter, whether the typed text so far still appears somewhere in the log (the walk falls off as soon as it doesn't).

Practice

These are the homework problems from the episode.

1. How many times does each query occur? The number of occurrences of a substring is the size of its endpos set. Give each non-clone state count 1 (a prefix ends there), then push the counts up the suffix links from the longest states to the shortest.

Solution (checked against brute force on 200 random texts)

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {                                        // how many times does each query occur?
    string t;
    int q;
    cin >> t >> q;
    SuffixAutomaton sam;
    vector<long long> cnt;
    for (char ch : t) {
        sam.extend(ch);
        cnt.resize(sam.st.size());
        cnt[sam.last] = 1;                          // the new prefix ends at one new position
    }
    vector<int> order(sam.st.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) { return sam.st[a].len > sam.st[b].len; });
    for (int v : order) if (v) cnt[sam.st[v].link] += cnt[v];   // longest first: push up the links
    while (q--) {
        string p;
        cin >> p;
        int v = 0;
        for (char ch : p) if (v != -1) v = sam.st[v].next[ch - 'a'] ? sam.st[v].next[ch - 'a'] : -1;
        cout << (v == -1 ? 0 : cnt[v]) << "\n";
    }
}
3
2
1
0

In banana: a 3 times, ana 2, nan 1, bb 0.

2. Longest common substring of two strings. Build the SAM of a and walk b through it like Aho-Corasick: keep the current state v and length l; on a missing edge, fall back along suffix links (and set l = len(v)) until the edge exists.

Solution (checked against brute force on 400 random pairs)

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {                                        // longest common substring of a and b
    string a, b;
    cin >> a >> b;
    SuffixAutomaton sam;
    for (char ch : a) sam.extend(ch);
    int v = 0, l = 0, best = 0, end = 0;
    for (int i = 0; i < (int)b.size(); i++) {       // longest suffix of b[0..i] that is in a
        int c = b[i] - 'a';
        while (v && !sam.st[v].next[c]) v = sam.st[v].link, l = sam.st[v].len;   // fall back
        if (sam.st[v].next[c]) v = sam.st[v].next[c], l++;
        if (l > best) best = l, end = i;
    }
    cout << best << " " << b.substr(end - best + 1, best) << "\n";
}
4 chai

3. The k-th smallest distinct substring. Count the paths from every state with a DP in reverse topological order (paths(v) = 1 + Σ paths(next)), then walk from the start choosing letters in order.

Hint

Sort the states by len descending for the DP; at each step skip whole subtrees whose path count is smaller than k.

4. The shortest string that is NOT a substring. BFS over the automaton from the start: the first missing edge found gives the answer (with a fixed alphabet, the shortest missing letter at the shallowest state).

Hint

Equivalently, a DP: short(v) = 1 + min over letters c of (missing edge ? 0 : short(next[v][c])).

Quick quiz

// t = "abcbc"   (positions 0..4)
// endpos(bc) = {2, 4}
// which one is in the SAME state as bc?

A) c · B) abc · C) cb · D) b

Answer

A. endpos(c) = {2, 4} = endpos(bc). abc ends only at 2, cb at 3, b at 1 and 3. So the state holds bc and c (len 2, link = the start).

Interview questions

  1. What does a suffix automaton recognise? Exactly the substrings of the text (its accepting states recognise the suffixes).
  2. What is a state? A class of substrings with the same set of end positions; they are suffixes of each other with consecutive lengths.
  3. How many states and edges? At most 2n − 1 states and 3n − 4 edges.
  4. What does the suffix link point to? The state of the longest suffix that lies in a different endpos class.
  5. When do you clone? When the state q reached from p by c is longer than len(p) + 1: its strings no longer all end at the same positions.
  6. Distinct substrings? Σ len(v) − len(link(v)) over all states but the start.
  7. SAM vs suffix array? SAM is online and walks queries letter by letter; the suffix array keeps sorted order (k-th, binary search, LCP tricks).

Glossary

Term Meaning Example
Substring A continuous piece of a string ala in masalachai
Suffix trie A trie of every suffix n²/2 nodes
Automaton A state machine that reads letters one edge per letter
Suffix automaton (SAM) The smallest automaton of all substrings ≤ 2n − 1 states
endpos Where a substring's occurrences end endpos(na) = {3, 5} in banana
State Substrings with the same endpos {na, ana}
len(v) Length of the longest string in state v 3 for {na, ana}
Suffix link Next shorter suffix in another state {na, ana} → {a}
extend(c) Add one letter to the automaton online build
Clone A copy of q with a shorter len state 4 = {b} in abb
Redirect Moving edges from q to the clone next[p][c] = clone
Amortised O(1) Constant on average over all steps per letter
Topological order (by len) Longer states before shorter pushing counts
long long 64-bit integer 19999478579
Stress test Fast vs brute force on random inputs all 500 tests passed
Cross product Left or right turn (next episode) —

Summary

  • A state = substrings with the same endpos; it stores len and a suffix link; at most 2n − 1 states.
  • extend(c): new state, walk links adding edges, then link to q, or clone q, redirect, and link both to the clone.
  • Queries: walk the edges, |p| steps. Distinct substrings: Σ len(v) − len(link(v)).
  • Occurrences: push endpos counts up the links, longest first.

Solutions in C++, Java and Python

Problem M1 · Snippet Check

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t;
    int q;
    cin >> t >> q;
    SuffixAutomaton sam;
    for (char ch : t) sam.extend(ch);
    while (q--) {
        string p;
        cin >> p;
        cout << (sam.contains(p) ? "YES" : "NO") << "\n";
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static int[] len, link;
    static int[][] next;
    static int size = 1, last = 0;

    static void extend(int c) {                          // add one letter at the end
        int cur = size++;
        len[cur] = len[last] + 1;
        int p = last;
        while (p != -1 && next[p][c] == 0) { next[p][c] = cur; p = link[p]; }
        if (p == -1) link[cur] = 0;
        else {
            int q = next[p][c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {                                       // split q with a clone
                int clone = size++;
                len[clone] = len[p] + 1;
                next[clone] = next[q].clone();
                link[clone] = link[q];
                while (p != -1 && next[p][c] == q) { next[p][c] = clone; p = link[p]; }
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }
    static boolean contains(String p) {
        int v = 0;
        for (int i = 0; i < p.length(); i++) {
            v = next[v][p.charAt(i) - 'a'];
            if (v == 0) return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String t = st.nextToken();
        int q = Integer.parseInt(st.nextToken());
        int cap = 2 * t.length() + 1;                    // at most 2n - 1 states (+ the start)
        len = new int[cap]; link = new int[cap]; next = new int[cap][26];
        link[0] = -1;
        for (int i = 0; i < t.length(); i++) extend(t.charAt(i) - 'a');
        StringBuilder out = new StringBuilder();
        while (q-- > 0) out.append(contains(br.readLine().trim()) ? "YES\n" : "NO\n");
        System.out.print(out);
    }
}
YES
YES
YES
YES
NO

Python

import sys

class SuffixAutomaton:
    def __init__(self):
        self.len, self.link, self.next = [0], [-1], [{}]   # state 0 = the empty string
        self.last = 0

    def extend(self, c):                                   # add one letter at the end
        cur = len(self.len)
        self.len.append(self.len[self.last] + 1); self.link.append(0); self.next.append({})
        p = self.last
        while p != -1 and c not in self.next[p]:
            self.next[p][c] = cur
            p = self.link[p]
        if p != -1:
            q = self.next[p][c]
            if self.len[p] + 1 == self.len[q]:
                self.link[cur] = q
            else:                                          # split q with a clone
                clone = len(self.len)
                self.len.append(self.len[p] + 1); self.link.append(self.link[q]); self.next.append(dict(self.next[q]))
                while p != -1 and self.next[p].get(c) == q:
                    self.next[p][c] = clone
                    p = self.link[p]
                self.link[q] = self.link[cur] = clone
        self.last = cur

    def contains(self, p):
        v = 0
        for c in p:
            if c not in self.next[v]:
                return False
            v = self.next[v][c]
        return True

data = sys.stdin.read().split()
t, q = data[0], int(data[1])
sam = SuffixAutomaton()
for c in t:
    sam.extend(c)
print("\n".join("YES" if sam.contains(p) else "NO" for p in data[2:2 + q]))
YES
YES
YES
YES
NO

Problem M2 · Distinct Snippets, again

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixAutomaton {
    struct State { int len, link; array<int, 26> next; };
    vector<State> st;                               // state 0 = the empty string
    int last = 0;
    SuffixAutomaton() { st.push_back({0, -1, {}}); }
    void extend(char ch) {                          // add one letter at the end
        int c = ch - 'a', cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next[c]) st[p].next[c] = cur, p = st[p].link;   // new edges
        if (p != -1) {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;   // q fits exactly
            else {                                  // q is too long: split it with a clone
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                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;
    }
    bool contains(const string& p) {                // walk the edges from the start
        int v = 0;
        for (char ch : p) {
            v = st[v].next[ch - 'a'];
            if (!v) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    SuffixAutomaton sam;
    for (char ch : s) sam.extend(ch);
    ll total = 0;
    for (int v = 1; v < (int)sam.st.size(); v++)    // each state: lengths link.len+1 .. len
        total += sam.st[v].len - sam.st[sam.st[v].link].len;
    cout << total << " (" << sam.st.size() << " states)\n";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static int[] len, link;
    static int[][] next;
    static int size = 1, last = 0;

    static void extend(int c) {                          // add one letter at the end
        int cur = size++;
        len[cur] = len[last] + 1;
        int p = last;
        while (p != -1 && next[p][c] == 0) { next[p][c] = cur; p = link[p]; }
        if (p == -1) link[cur] = 0;
        else {
            int q = next[p][c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {                                       // split q with a clone
                int clone = size++;
                len[clone] = len[p] + 1;
                next[clone] = next[q].clone();
                link[clone] = link[q];
                while (p != -1 && next[p][c] == q) { next[p][c] = clone; p = link[p]; }
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }
    static boolean contains(String p) {
        int v = 0;
        for (int i = 0; i < p.length(); i++) {
            v = next[v][p.charAt(i) - 'a'];
            if (v == 0) return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        String s = new BufferedReader(new InputStreamReader(System.in)).readLine().trim();
        int cap = 2 * s.length() + 1;
        len = new int[cap]; link = new int[cap]; next = new int[cap][26];
        link[0] = -1;
        for (int i = 0; i < s.length(); i++) extend(s.charAt(i) - 'a');
        long total = 0;
        for (int v = 1; v < size; v++) total += len[v] - len[link[v]];   // lengths link.len+1 .. len
        System.out.println(total + " (" + size + " states)");
    }
}
15 (10 states)

Python

import sys

class SuffixAutomaton:
    def __init__(self):
        self.len, self.link, self.next = [0], [-1], [{}]   # state 0 = the empty string
        self.last = 0

    def extend(self, c):                                   # add one letter at the end
        cur = len(self.len)
        self.len.append(self.len[self.last] + 1); self.link.append(0); self.next.append({})
        p = self.last
        while p != -1 and c not in self.next[p]:
            self.next[p][c] = cur
            p = self.link[p]
        if p != -1:
            q = self.next[p][c]
            if self.len[p] + 1 == self.len[q]:
                self.link[cur] = q
            else:                                          # split q with a clone
                clone = len(self.len)
                self.len.append(self.len[p] + 1); self.link.append(self.link[q]); self.next.append(dict(self.next[q]))
                while p != -1 and self.next[p].get(c) == q:
                    self.next[p][c] = clone
                    p = self.link[p]
                self.link[q] = self.link[cur] = clone
        self.last = cur

    def contains(self, p):
        v = 0
        for c in p:
            if c not in self.next[v]:
                return False
            v = self.next[v][c]
        return True

s = sys.stdin.readline().strip()
sam = SuffixAutomaton()
for c in s:
    sam.extend(c)
total = sum(sam.len[v] - sam.len[sam.link[v]] for v in range(1, len(sam.len)))
print(f"{total} ({len(sam.len)} states)")
15 (10 states)