扩展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); } }