[HAOI2016]找相同字元(字尾自動機)

/*

一個建立字尾自動機一個跑就行
依舊是對于所有的祖先都有貢獻
 

*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long 
#define mmp make_pair
#define M 400010
using namespace std;
int read()
{
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
int len[M], fa[M], ch[M][26], sz[M], f[M], g[M], tim[M], a[M], cnt = 1, lst = 1;
char s[M]; 
ll ans = 0;

void insert(int c)
{
    int p = ++cnt, f = lst;
    lst = p;
    len[p] = len[f] + 1;
    sz[p] = 1;
    while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
    if(!f) fa[p] = 1;
    else
    {
        int q = ch[f][c];
        if(len[q] == len[f] + 1) fa[p] = q;
        else
        {
            int nq = ++cnt;
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            fa[nq] = fa[q];
            len[nq] = len[f] + 1;
            fa[q] = fa[p] = nq;
            while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
        }
    }
}
int main()
{
    scanf("%s", s + 1);
    int l = strlen(s + 1);
    for(int i = 1; i <= l; i++) insert(s[i] - 'a');
    for(int i = 1; i <= cnt; i++) tim[len[i]]++;
    for(int i = 1; i <= cnt; i++) tim[i] += tim[i - 1];
    for(int i = 1; i <= cnt; i++) a[tim[len[i]]--] = i;
    for(int i = cnt; i >= 1; i--) sz[fa[a[i]]] += sz[a[i]];
    scanf("%s", s + 1);
    l = strlen(s + 1);
    int now = 1, lt = 0;
    for(int i = 1; i <= l; i++)
    {
        int c = s[i] - 'a';
        if(ch[now][c]) lt++, now = ch[now][c];
        else {
            while(now && !ch[now][c]) now = fa[now];
            if(!now) now = 1, lt = 0;
            else lt = len[now] + 1, now = ch[now][c];
        }
        ans += 1ll * sz[now] * (lt - len[fa[now]]);
        g[now]++;
    }
    for(int i = cnt; i >= 1; i--)
    {
        ans += 1ll * sz[a[i]] * f[a[i]] * (len[a[i]] - len[fa[a[i]]]);
        f[fa[a[i]]] += f[a[i]] + g[a[i]];
    }
    cout << ans << "\n";
    return 0;
}                

轉載于:https://www.cnblogs.com/luoyibujue/p/10628633.html