HDU3336 Count the string 一道KMP的巧解

http://acm.hdu.edu.cn/showproblem.php?pid=3336 题目

这是喵呜大神用KMP做的，46MS 

#include <stdio.h>

#define MOD 10007

char b[200005];
int dp[200005];
int p[200005];
int n;

int Pre()
{
    int s,i,j;
    dp[0]=1;
    j=-1;
    p[0]=-1;
    s=1;
    for (i=1;i<n;i++)
    {
        while(j>=0 && b[j+1]!=b[i]) j=p[j];
        if (b[j+1]==b[i]) j++;
        if (j>=0) dp[i]=(dp[j]+1)%MOD;
        else dp[i]=1;
        p[i]=j;
        s=(s+dp[i])%MOD;
    }
    return s;
}

int main()
{
    int i,j,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%s",b);
        printf("%d\n",Pre());
    }
    return 0;
}

#include <stdio.h>
char str[200005];
int main()
{
    int t,n,i,j,sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=n;
        sum%=10007;
        scanf("%s",str);
        for(i=1;i<n;i++)
        {
            if(str[i]==str[0])
            {
                for(j=i;j<n;j++)
                {
                    if(str[j]!=str[j-i])
                        break;
                }
                sum+=j-i;
                sum%=10007;
            }
        }
        printf("%d/n",sum);
    }
    return 0;
}