HDU 3336 KMP 求所有前缀在母串中出现的次数

#include <stdio.h>  
#include <string.h>  
char P[200100];//从0开始存  
int f[200100];//记录P的自我匹配  
int len;  
  
void getFail(){  
    f[0]=f[1]=0;  
    for(int i=1;i<len;i++){  
        int j=f[i];  
        while(j&&P[i]!=P[j])j=f[j];  
        f[i+1]= P[i]==P[j] ? j+1 : 0;  
    }  
}  
int dp[200100], ans;  
int main(){  
    int T;scanf("%d",&T);  
    while(T--){  
        scanf("%d",&len);  
        scanf("%s",P);  
        int ans = 0;  
        getFail();  
        memset(dp, 0, sizeof(dp));  
        dp[0] = 0;  
        ans = 0;  
        for(int i = 1;i <= len;i++)  
        {  
            dp[i] = (dp[f[i]] + 1)%10007;  
            ans += dp[i];  
            if(ans>10007)ans %= 10007;  
        }  
  
        printf("%d\n",ans);  
  
    }  
    return 0;  
}  
/* 
99 
4 
abab 
6 
ababab 
*/