题解：利用next数组来保存前缀位置，递推求解。

#include <cstdio>#include <cstring>char pat[200005];int next[200005],M,f[200005];const int MOD=10007;int getnext(){    int i=1,j=0;next[1]=0;    while(i<M){        if(j==0||pat[j]==pat[i])next[++i]=++j;        else j=next[j];    }}int main(){    int T,i; scanf("%d",&T);    while(T--){        scanf("%d",&M);        scanf("%s",pat+1);        pat[0]=‘#‘; M=strlen(pat);        pat[M]=‘*‘; getnext(); f[1]=0;        int s=0; for(i=2;i<=M;i++)(s+=(f[i]=f[next[i]]+1))%=MOD;        printf("%d\n",s);    }    return 0;}