学步园

题意：给一个字符串，对每一个前缀出现的次数求和。

这里有另外一种思路：【KMP】HDU 3336 Count the string - KIDxの博客 - ITeye技术网站

#include <cstdio>
#include <cstring>

const int MOD=10007;
const int N=200005;
char s[N];
int next[N],n,f[N];

void getNext(char s[],int len)
{
    next[0]=-1;
    int i=0,j=-1;
    while (i<len)
    {
        if (j==-1 || s[i]==s[j])
            next[++i]=++j;
        else j=next[j];
    }
}

int DP ()
{
    int ans=0;
    memset(f,0,sizeof(f));
    for (int i=1;i<=n;i++)
    {//f[i]表示长度为i的字符串(也就是把str[i]当成'\0')总共含前缀的数量
        f[i]=f[next[i]]+1;//+1表示长度为next[i]的前缀在当前结尾又出现了一次
        ans=(ans+f[i])%MOD;
    }
    return ans;
}

int main ()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        scanf("%s",s);
        getNext(s,n);
        printf("%d\n",DP());
    }
    return 0;
}