SAM 模板

评价：逆天纸糊串，学不会一点。

#include <bits/stdc++.h>

const int MAXN = 3e6 + 100;

int N;
char ch[MAXN];
long long answer;

class Suffix_Automaton {
private:
    int tot, last, root;
    int child[MAXN][26], link[MAXN], length[MAXN];
    long long cnt[MAXN];
public:
    Suffix_Automaton() {
        root = tot = last = 1;
    }

    void Insert(int c) {
        int p = last, newP = ++ tot;
        last = newP;
        length[newP] = length[p] + 1;
        cnt[newP] = 1;

        while (p && !child[p][c]) {
            child[p][c] = newP;
            p = link[p];
        }
        // std::cout << p << '\n';
        if (!p) {
            link[newP] = root;
        }
        else {
            int q = child[p][c];
            if (length[q] == length[p] + 1) {
                link[newP] = q;
            }
            else {
                int newQ = ++ tot;
                memcpy(child[newQ], child[q], sizeof child[q]);
                link[newQ] = link[q];
                link[q] = link[newP] = newQ;
                length[newQ] = length[p] + 1;

                while (p && child[p][c] == q) {
                    child[p][c] = newQ;
                    p = link[p];
                }
            }
        }
    }

    std::vector<int> son[MAXN];
    void Build() {
        for (int i = 1; i <= tot; ++ i) {
            son[link[i]].emplace_back(i);
            // std::cout << link[i] << ' ';
        }
        // std::cout << '\n';
    }

    void Dfs(int now) {
        for (const int &iter: son[now]) {
            Dfs(iter);
            cnt[now] += cnt[iter];
        }
        if (cnt[now] != 1) {
            answer = std::max(answer, length[now] * cnt[now]);
        }
    }
}sam;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> (ch + 1);
    int N = strlen(ch + 1);
    for (int i = 1; i <= N; ++ i)
        sam.Insert(ch[i] - 'a');
    sam.Build();
    sam.Dfs(1);
    std::cout << answer << '\n';

    return 0;
}

生成魔咒

\(SAM\) 板子题，每个节点表示的都是不同的子串，每次新加一个节点就统计一次答案就行了，用后缀树上每个节点的最长长度减去最小长度就行。

用 \(Max(b) = Min(a) - 1\) 来求每个节点的最小长度。

#include <bits/stdc++.h>

const int MAXN = 3e5 + 10;

int N;
int a[MAXN];
long long answer;

class Suffix_Automaton {
private:
    int tot, last, root;
    std::unordered_map<int, int> child[MAXN];
    int link[MAXN];
    long long length[MAXN];
public:
    Suffix_Automaton() {
        root = tot = last = 1;
    }

    void Insert(int c) {
        int p = last, newP = ++ tot;
        last = newP;
        length[newP] = length[p] + 1;

        while (p && !child[p][c]) {
            child[p][c] = newP;
            p = link[p];
        }

        if (!p) {
            link[newP] = root;
        }
        else {
            int q = child[p][c];
            if (length[q] == length[p] + 1) {
                link[newP] = q;
            }
            else {
                int newQ = ++ tot;
                child[newQ] = child[q]; 
                link[newQ] = link[q];
                link[q] = link[newP] = newQ;
                length[newQ] = length[p] + 1;

                while (p && child[p][c] == q) {
                    child[p][c] = newQ;
                    p = link[p];
                }
            }
        }

        answer += (length[newP] - length[link[newP]]);
    }
}sam;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N;
    for (int i = 1, temp; i <= N; ++ i) {
        std::cin >> temp;
        sam.Insert(temp);
        std::cout << answer << '\n';
    }
}