匹配用的KMP，另外+DP存储状态；
DP数组f[i]代表当前前缀可以匹配的次数。
f[i]=f[next[i]]+1;为next[i]--i的的前缀的数量。
计算总和即可。
#include<iostream>
using namespace std;char t[222222];
int next[222222],f[222222];
int L;void setNext()
{int j=0,k=-1;next[0]=-1;while( j<L ){if( k==-1||t[j]==t[k] )next[++j]=++k;elsek=next[k]; }
}int main()
{int T;scanf( "%d",&T );while( T-- ){scanf( "%d",&L );scanf( "%s",&t );setNext();int sum=0;memset( f,0,sizeof(f) );for( int i=1;i<=L;i++ ){f[i]=(f[next[i]]+1)%10007;sum=(sum+f[i])%10007;}printf( "%d\n",sum );}return 0;
}