扩展kmp

这题只能用扩展kmp做了

我们求一下next就好了，然后直接统计

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 2e5+100;
int net[max_n], extend[max_n];
void getnext(char p[]) {
    register int a = 0;register int b = 0;
    int nn = strlen(p);
    net[0] = nn;
    for (register int i = 1;i < nn;++i) {
        if (i >= b || i + net[i - a] >= b) {
            if (i >= b)
                b = i;
            while (b < nn && p[b - i] == p[b])
                ++b;
            net[i] = b - i;
            a = i;
        }
        else
            net[i] = net[i - a];
    }
}
char s[max_n];
const int mod = 10007;
int main(){
    int T;scanf("%d",&T);
    while (T--){
        int n;scanf("%d",&n);
        scanf("%s",s);
        getnext(s);
        int ans = 0;
        for (int i=0;i<n;++i)ans = (ans+net[i]%mod)%mod;
        printf("%d\n",ans);
    }
}