BZOJ3238: [Ahoi2013]差异(后缀自动机)

题意

题目链接

sol

前面的可以直接算

然后原串翻转过来，这时候变成了求任意两个前缀的最长公共后缀，显然这个值应该是\(len[lca]\)，求出\(siz\)乱搞一下

#include<bits/stdc++.h>
#define int long long 
#define ll long long 
using namespace std;
const int maxn = 1e6 + 10;
ll n;
char a[maxn];
int fa[maxn], len[maxn], siz[maxn], ch[maxn][26], tot = 1, las = 1, root = 1, sum[maxn];
ll ans;
vector<int> v[maxn];
void insert(int x) {
    int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1;
    for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
    if(!pre) fa[now] = root;
    else {
        int q = ch[pre][x];
        if(len[pre] + 1 == len[q]) fa[now] = q;
        else {
            int ns = ++tot; fa[ns] = fa[q]; len[ns] = len[pre] + 1;
            memcpy(ch[ns], ch[q], sizeof(ch[q]));
            fa[q] = fa[now] = ns;
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = ns;
        }
    }
    siz[now] = 1;
}
void build() {
    for(int i = 2; i <= tot; i++) v[fa[i]].push_back(i);
}
ll res = 0;
void dp(int x) {
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i];
        dp(to); 
        res += 1ll * len[x] * siz[x] * siz[to];
        siz[x] += siz[to];
    }
}
signed main() {
    //freopen("a.in", "r", stdin);
    scanf("%s", a + 1);
    n = strlen(a + 1);
    reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) insert(a[i] - 'a');
    build(); dp(root);
    for(int i = 1; i <= n; i++) ans += (ll) (1ll * i * (n - i)  + 1ll * (n * (n + 1) / 2 - (i * (i + 1) / 2)));
    cout << ans - res * 2;
    return 0;  
}
/*
abbabbabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
*/