next 数组
#include <cstdio> #include <cstring> #include <iostream> #include <time.h> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; int const MOD = 10007; int const MAXN = 200010; char s[MAXN]; int next[MAXN],dp[MAXN]; inline void Get_Next(int n){ memset(next,0,sizeof(next)); for(int i = 1;i < n;i++){ int j = next[i]; while(j && s[i] != s[j]) j = next[j]; if(s[i] == s[j]) next[i + 1] = j + 1; else next[i + 1] = 0; } } int main(){ int T; while(~scanf("%d",&T)){ while(T--){ int n; scanf("%d",&n); scanf("%s",s); Get_Next(n); for(int i = 0;i < n;i++){ dp[i] = 1; } dp[0] = 0; int sum = 0; for(int i = 1;i <= n;i++){ dp[i] = dp[next[i]] + 1; sum = (sum + dp[i]) % MOD; } printf("%d\n",sum); } } return 0; }