学步园

求字符串的所有前缀在字符串中出现的次数之和

next[i]=j;

dp[j]:以s[j]结尾的子串总共含前缀的数量

dp[i]=1+dp[next[i]]: 以i结尾的子串中含前缀的数量加上前j个字符这一前缀

#include<stdio.h>
#include<string.h>
#define N 200002
int dp[N],next[N],n;
char s[N];
void get()
{
    next[1]=0;
    int i,j=0;
    for(i=2;i<=n;i++)
    {
        while(j>0&&s[i]!=s[j+1])
            j=next[j];
        if(s[i]==s[j+1])
            j++;
        next[i]=j;
    }
}
int main()
{
    int i,j;
    scanf("%d",&j);
    while(j--)
    {
        scanf("%d",&n);
        scanf("%s",s+1);
        get();
        dp[0]=0;
        int sum=0;
        for(i=1;i<=n;i++)
        {
            dp[i]=dp[next[i]]+1;
            sum=(sum+dp[i])%10007;
        }
        printf("%d\n",sum);
    }
    return 0;
}