HDU 3336 Count the string(KMP+DP)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3336
題意:文字列をあげて、そのすべての接頭辞がその文字列に現れる回数の総和を計算します.
構想:next[j]=iは、s[1...i]=s[j-i+1....j]を表し、f[i]はs[i]で終わるサブ列の合計接頭辞の数を表し、f[j]=f[i]+1は、iで終わるサブ列の接頭辞の数に前のj文字という接頭辞を加える.

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;



const int MOD=10007;

const int MAX=200005;

char s[MAX];

int next[MAX],n,f[MAX];



void getNext(char s[],int len,int next[])

{

    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 C;



int DP()

{

    int i,ans=0;

    for(i=1;i<=n;i++)

    {

        f[i]=f[next[i]]+1;

        ans=(ans+f[i])%MOD;

    }

    return ans;

}



int main()

{

    for(scanf("%d",&C);C--;)

    {

        scanf("%d",&n);

        scanf("%s",s);

        getNext(s,n,next);

        printf("%d
",DP());

    }

    return 0;

}