一道ACM题，字符串前缀，找不出递推的规律。解决办法

一道ACM题，字符串前缀，找不出递推的规律。
题目：http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1301
研究了大半天了。但本人太笨了。没总结出规律。呼唤牛人。

[解决办法]

C/C++ code

#include<iostream>#include<cstring>using namespace std;const int MM=1000000007;int dp[200005],next[200005];char t[200005];void GetNext(int len){     next[0]=-1;     int i=0,j=next[i];     while(i<len){         if(j==-1 || t[i]==t[j]){             i++;             j++;             next[i]=j;         }         else             j=next[j];     }}int main(){    int tt,len,sum;    scanf("%d",&tt);    while(tt--){        scanf("%s",t);        len=strlen(t);        GetNext(len);        memset(dp,0,sizeof(dp));        sum=0;        for(int i=1;i<=len;i++){            dp[i]=(dp[next[i]]+1)%MM;            sum=(sum+dp[i])%MM;        }        printf("%d\n",sum);    }return 0;}