例如：
6
a b a b a b ‘\0’
下标i: 0 1 2 3 4 5 6
Next: -1 0 0 1 2 3 4
dp: 0 1 1 2 2 3 3
dp[ 1 ]=1表示目前:‘a’出现一次
dp[ 2 ]=1:同上：“ab”
dp[ 3 ]=2表示“abab”一次，“ab”一次
。
。
。
dp[ 6 ]=3表示首字母‘a’在整个的出现次数
KMP够强大！！！！！
View Code
1 #include<stdio.h> 2 #include<string.h> 3 const int maxn = 200005; 4 const int mod= 10007; 5 char a[ maxn ],next[ maxn ]; 6 void getNext( int len ){ 7 next[ 0 ]=-1; 8 int i,j; 9 i=0,j=-1; 10 while( i<len ){ 11 if( j==-1 || a[ i ]==a[ j ] ) 12 i++,j++,next[ i ]=j; 13 else j=next[ j ]; 14 } 15 } 16 int dp[ maxn ];//dp[i]:以i结尾的串中所有前缀 17 int main(){ 18 int t; 19 scanf("%d",&t); 20 while( t-- ){ 21 int len; 22 scanf("%d",&len); 23 memset( dp,0,sizeof( dp )); 24 scanf("%s",a); 25 getNext( len ); 26 int ans=0; 27 for( int i=1;i<=len;i++ ){ 28 //printf("%d\n",next[i]); 29 dp[ i ]=dp[ next[ i ] ]+1; 30 dp[ i ]%=mod; 31 ans+=dp[ i ],ans%=mod; 32 } 33 printf("%d\n",ans); 34 } 35 return 0; 36 }