传送门

扩展KMP模板题

要你求对于每个后缀，与前缀匹配的最大长度

是我太菜了，居然不知道有这个算法。。。。。被签到题自闭十万年

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
bool vis[maxn];
char a[maxn], b[maxn];
int nxt[maxn], f[maxn];
int main()
{
    int T; cin >> T;
    while(T--)
    {
        scanf("%s" , a);
        int n = strlen(a);
        memset(nxt, 0, sizeof nxt);
        nxt[0] = n;
        int j = 0;
        while(j + 1 < n && a[j] == a[j + 1]) j++;
        nxt[1] = j;
        int p0 = 1;
        for(int i = 2; i < n; i++)
        {
            if(i + nxt[i - p0] < nxt[p0] + p0) nxt[i] = nxt[i - p0];
            else 
            {
                j = max(0, nxt[p0] + p0 - i);
                while(a[j] == a[i + j] && i + j < n) j++;
                nxt[i] = j;
                p0 = i;
            }
        }
        ll ans = 0;
        for(int i = 1; i < n; i++)
        {
            if(nxt[i] == n - i) ans += nxt[i];
            else ans += nxt[i] + 1;
        }
        printf("%lld\n", ans);
    }
}