P4248 [AHOI2013] 差异

SAM:这个SAM版的其实很简单。

因为要求 \(lcp\)，所以先把字符串翻转，这样翻转过后的字符串的后缀就是原来字符串的前缀了。

然后题目要我们求最长长度，并且我们已经转化成后缀了，那么就在 \(parent\) 树上考虑。

显然，对于我们 \(parent\) 树上某个节点 \(x\) 的儿子们 \(i, j, k\)，在 \(i, j, k\) 节点上的后缀不相等，当且仅当 \(i, j, k\) 节点上的后缀去掉前面一部分后才能相当，也就是去掉前面的部分直到长度成为节点 \(x\) 的 \(length\) 的时候是最长且相等。

那么这个时候我们统计 \(i, j, k\) 之间能配对的数量再乘上 \(length[x] * 2\) （内个 \(2\) 是题目要乘的）就是我们要减去的答案。

元旦

#include <bits/stdc++.h>

const int MAXN = 3 * (5e5 + 1000);

long long answer;

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

    void Insert(int c) {
        int p = last, newP = ++ tot;
        last = newP;
        length[newP] = length[p] + 1;
        count[newP] = 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;
                memcpy(child[newQ], child[q], sizeof child[q]);
                length[newQ] = length[p] + 1;
                link[newQ] = link[q];
                link[q] = link[newP] = newQ;

                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);
    }

    void Dfs(int now) {
        // long long has = 0;
        // std::cout << "count = " << count[now] << '\n';
        for (const int &iter: son[now]) {
            Dfs(iter);
            // std::cout << "count = " << count[iter] << '\n';
            answer -= 2ll * count[now] * count[iter] * length[now];
            // std::cout << now << ' ' << count[now] << ' ' << count[iter] << '\n';
            count[now] += count[iter];
        }
    }
}sam;

int N;
char ch[MAXN];

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

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

    std::cout << answer << '\n';
    return 0;
}

526互联

2023.1.1做题纪要

P4248 [AHOI2013] 差异