Fundamentals of Suffix Arrays

The Suffix Array (SA) is a critical data structure for efficient string analysis. It primarily relies on three interconnected arrays:

• Suffix Order (sa): sa[i] stores the starting index of the suffix that ranks i-th lexicographically.
• Rank Array (rk): rk[i] stores the lexicographical rank of the suffix beginning at index i.
• Longest Common Prefix Array (ht or height): ht[i] records the length of the longest common prefix between the suffix ranked i and the suffix ranked i-1.

The standard construction employs a doubling algorithm combined with radix sorting, achieving O(n log n) time complexity with a small constant factor. The process begins by sorting suffixes based on their first character. In each subsequent phase, the algorithm sorts pairs of ranks representing the first 2^k characters, effectively doubling the considered prefix length until the entire string is ordered. A key optimization involves deriving the second-keyword ranks by observing that the suffix starting at i contributes its first keyword to the second keyword of the suffix starting at i - 2^k. Processing these in reverse order maintains stability during sorting.

void buildSuffixArray(const std::vector<int>& s, int n) {
    std::vector<int> cnt(256, 0), oldRank(n + 1), secKey(n + 1);
    for (int i = 1; i <= n; ++i) ++cnt[s[i]];
    for (int i = 1; i < 256; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[s[i]]--] = i;

    for (int k = 1; k <= n; k <<= 1) {
        int pos = 0;
        for (int i = n - k + 1; i <= n; ++i) secKey[++pos] = i;
        for (int i = 1; i <= n; ++i) {
            if (sa[i] > k) secKey[++pos] = sa[i] - k;
        }
        std::fill(cnt.begin(), cnt.end(), 0);
        for (int i = 1; i <= n; ++i) ++cnt[oldRank[i]];
        for (int i = 1; i < 256; ++i) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; --i) sa[cnt[oldRank[secKey[i]]]--] = secKey[i];
        
        std::swap(oldRank, secKey);
        oldRank[sa[1]] = 1;
        int distinct = 1;
        for (int i = 2; i <= n; ++i) {
            bool sameFirst = secKey[sa[i]] == secKey[sa[i - 1]];
            bool sameSecond = (sa[i] + k <= n ? secKey[sa[i] + k] : 0) == 
                              (sa[i - 1] + k <= n ? secKey[sa[i - 1] + k] : 0);
            oldRank[sa[i]] = (sameFirst && sameSecond) ? distinct : ++distinct;
        }
        if (distinct == n) break;
    }
}

The LCP array can be computed efficiently using the property ht[rk[i]] >= ht[rk[i-1]] - 1. This allows a linear-time scan where the matching length only needs to be decremented by at most one before resuming character comparisons.

void computeLCP(const std::vector<int>& s, int n) {
    for (int i = 1; i <= n; ++i) rankMap[sa[i]] = i;
    int matchLen = 0;
    for (int i = 1; i <= n; ++i) {
        if (rankMap[i] == 1) continue;
        if (matchLen > 0) --matchLen;
        int prevIdx = sa[rankMap[i] - 1];
        while (i + matchLen <= n && prevIdx + matchLen <= n && s[i + matchLen] == s[prevIdx + matchLen]) {
            ++matchLen;
        }
        lcpArray[rankMap[i]] = matchLen;
    }
}

Typical Problem Patterns with Suffix Arrays

1. Grouping Similar Suffixes: When asked to count pairs sharing a common prefix of length at least L, the problem reduces to merging adjacent suffixes in the sorted array whose ht value meets the threshold. A Disjoint Set Union (DSU) structure can maintain component sizes and extremal values while iterating backwards from the maximum possible L.

pair<long long, long long> processSimilarity(int threshold) {
    long long pairCount = 0, bestProduct = -INF;
    for (int idx : positionsWithLCP[threshold]) {
        int rootA = dsuFind(idx - 1);
        int rootB = dsuFind(idx);
        if (rootA == rootB) continue;
        
        pairCount -= componentSize[rootA] * componentSize[rootB];
        dsuMerge(rootA, rootB);
        pairCount += componentSize[rootB];
        bestProduct = max(bestProduct, getMaxProduct(rootB));
    }
    return {pairCount, bestProduct};
}

2. Range Minimum Queries on LCP: Many problems require computing the sum of LCP values across all suffix pairs. Since the LCP of any two suffixes equals the minimum value in the ht array between their ranks, the problem transforms into a range minimum query. A Sparse Table (st) allows O(1) queries after O(n log n) preprocessing.

3. Distinct Substring Count: Every substring corresponds to a prefix of some suffix. Without deduplication, there are n(n+1)/2 such prefixes. However, if ht[i] = L, the first L prefixes of the i-th suffix are identical to those of the (i-1)-th suffix. Thus, the number of unique substrings is n(n+1)/2 - sum(ht[2..n]).

4. Pairwise Distance Sum: Problems asking for the sum of distances between all suffix pairs can be solved by observing that the contribution of each ht[i] is multiplied by the number of rank intervals it spans. A monotonic stack efficiently identifies the left and right boundaries where ht[i] remains the minimum, enabling an O(n) calculation.

std::vector<int> leftBound(n + 1), rightBound(n + 1);
std::vector<int> stack;
stack.push_back(1);
for (int i = 2; i <= n; ++i) {
    while (!stack.empty() && lcpArray[i] < lcpArray[stack.back()]) {
        rightBound[stack.back()] = i;
        stack.pop_back();
    }
    if (!stack.empty()) leftBound[i] = stack.back();
    stack.push_back(i);
}
while (!stack.empty()) { rightBound[stack.back()] = n + 1; stack.pop_back(); }

long long totalDist = 0;
for (int i = 1; i <= n; ++i) totalDist += (long long)(n - 1) * i;
long long overlapSum = 0;
for (int i = 2; i <= n; ++i) {
    overlapSum += (long long)(i - leftBound[i]) * (rightBound[i] - i) * lcpArray[i];
}
printf("%lld\n", totalDist - 2 * overlapSum);

Suffix Automaton: Core Principles

A Suffix Automaton (SAM) is a directed acyclic graph that compactly represents all substrings of a given string. It uses at most 2n states and 3n transitions. Each state encapsulates a set of substrings sharing the same endpos set (the collection of ending indices in the original text). The automaton suppports online construction in O(n) time.

Key structural elements include:

• Link Tree (Parent Tree): Formed by the link pointers. link[u] points to the longest proper suffix of the strings in state u that belongs to a different endpos class.
• Max Length (maxLen): The length of the longest substring represented by a state.

The construction algorithm maintains a pointer to the state representing the entire string processed so far. When appending a new character, it creates a new state, copies transitions from clones if necessary to preserve the equivalence classes, and updates links accordingly.

struct AutomatonNode {
    int link;
    int maxLen;
    std::vector<int> trans;
};

std::vector<AutomatonNode> nodes(2 * MAXN);
int lastState = 1, nodeCount = 1;

void extend(int character) {
    int cur = ++nodeCount;
    nodes[cur].maxLen = nodes[lastState].maxLen + 1;
    int p = lastState;
    while (p != 0 && nodes[p].trans[character] == 0) {
        nodes[p].trans[character] = cur;
        p = nodes[p].link;
    }
    if (p == 0) {
        nodes[cur].link = 1;
    } else {
        int q = nodes[p].trans[character];
        if (nodes[p].maxLen + 1 == nodes[q].maxLen) {
            nodes[cur].link = q;
        } else {
            int clone = ++nodeCount;
            nodes[clone] = nodes[q];
            nodes[clone].maxLen = nodes[p].maxLen + 1;
            while (p != 0 && nodes[p].trans[character] == q) {
                nodes[p].trans[character] = clone;
                p = nodes[p].link;
            }
            nodes[q].link = nodes[cur].link = clone;
        }
    }
    lastState = cur;
}

Algorithmic Patterns with Suffix Automata

1. Substring Frequency: The occurrence count of all substrings in a state is identical. By initializing leaf states with count 1 and propagating sums up the link tree, we obtain the frequency for every state.

void propagateCounts(int u) {
    for (int v : childrenList[u]) {
        propagateCounts(v);
        occurrenceCount[u] += occurrenceCount[v];
    }
}

2. Multi-String Longest Common Substring: Build a SAM for the first string. For each subsequent string, traverse the automaton while tracking the current match length. On mismatch, follow the link pointer and adjust the length. Record the maximum match per state per string, then aggregate across strings by taking the minimum per state. Finally, push values down the link tree to ensure longer suffixes inherit valid match lengths.

void updateGlobalMax() {
    for (int i = 1; i <= nodeCount; ++i) ans[i] = nodes[i].maxLen;
    for (int i = 1; i <= nodeCount; ++i) treeEdges.push_back({nodes[i].link, i});
    
    for (int s = 1; s < k; ++s) {
        readNextString();
        int cur = 1, currentLen = 0;
        std::fill(tempMax.begin(), tempMax.end(), 0);
        for (char c : currentString) {
            int charIdx = c - 'a';
            while (cur != 1 && nodes[cur].trans[charIdx] == 0) {
                cur = nodes[cur].link;
                currentLen = nodes[cur].maxLen;
            }
            if (nodes[cur].trans[charIdx]) {
                cur = nodes[cur].trans[charIdx];
                ++currentLen;
            }
            tempMax[cur] = std::max(tempMax[cur], currentLen);
        }
        // Propagate downwards in link tree
        std::vector<int> order = getTopologicalOrder(); // decreasing maxLen
        for (int u : order) {
            if (nodes[u].link) tempMax[nodes[u].link] = std::max(tempMax[nodes[u].link], tempMax[u]);
        }
        for (int i = 1; i <= nodeCount; ++i) ans[i] = std::min(ans[i], tempMax[i]);
    }
}

3. Distinct Substring Count & K-th Lexicographical: The number of distinct substrings equals the sum of (maxLen[u] - maxLen[link[u]]) for all states. To find the K-th substring, compute the number of paths starting from each state (using DFS or DP on the DAG), then traverse greedily by comparing K against the path counts of outgoing transitions.

Generalized Suffix Automata

Generalized SAMs extend the single-string automaton to handle multiple input strings simultaneously. While naive approaches insert a unique separator between strings or reset the state pointer to root before each string, the most efficient method constructs a Trie of all strings first, then performs a BFS/DFS traversal on the Trie to build the SAM incrementally. This preserves the linear space complexity relative to the total length of all strings.

void buildFromTrie(int trieNode, int parentState) {
    for (int charIdx = 0; charIdx < 26; ++charIdx) {
        int childTrie = trieChildren[trieNode][charIdx];
        if (childTrie == 0) continue;
        
        int curState = ++nodeCount;
        nodes[curState].maxLen = nodes[parentState].maxLen + 1;
        int p = parentState;
        while (p != 0 && nodes[p].trans[charIdx] == 0) {
            nodes[p].trans[charIdx] = curState;
            p = nodes[p].link;
        }
        if (p == 0) {
            nodes[curState].link = 1;
        } else {
            int q = nodes[p].trans[charIdx];
            if (nodes[p].maxLen + 1 == nodes[q].maxLen) {
                nodes[curState].link = q;
            } else {
                int clone = ++nodeCount;
                nodes[clone] = nodes[q];
                nodes[clone].maxLen = nodes[p].maxLen + 1;
                while (p != 0 && nodes[p].trans[charIdx] == q) {
                    nodes[p].trans[charIdx] = clone;
                    p = nodes[p].link;
                }
                nodes[q].link = nodes[curState].link = clone;
            }
        }
        buildFromTrie(childTrie, curState);
    }
}

Applications: Generalized SAMs excel in problems requiring cross-string analysis. For instance, finding the longest common substring between two sets of strings involves building the structure, marking which original strings pass through each state, and propagating valid lengths up the link tree. When counting occurrences across multiple inputs, one can mark terminal nodes during Trie traversal, then push occurrence counts downward in the link tree to accumulate results for all substrings represented by each state. This approach efficiently solves complex multi-pattern matching and combinatorial string problems.