这是个链接 -> Z函数作用同扩展KMP

有字符串s，z[i]表示s[i]开始的字符串与s[0]开始的字符串的最长公共前缀

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
char str[maxn];
int ne[maxn], z[maxn];
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        for(int i = 1; i <= len; i++) z[i] = 0;
        z[1] = len;
        for(int i = 2, l = 0, r = 0; i <= len; i++)
        {
            if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
            while(i + z[i] <= len && str[z[i] + i] == str[z[i] + 1]) z[i] ++;
            if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
        }
        long long ans = 0;
        for(int i = 2; i <= len; i++) ans += z[i] + i > len ? z[i] : z[i] + 1;
        printf("%lld\n", ans);
    }
}

参考资料

• OI-WIKI
• xht