KMP+DP1

Description 
求一个字符串的所有前缀在串中出现的次数之和 
Input 
多组用例，每组用例占一行为一个长度不超过100000的字符串，以文件尾结束输入 
Output 
对于每组用例，输出该字符串的所有前缀在串中出现的次数之和，结果模256 
Sample Input 
aaa 
abab 
Sample Output 
6 
6 
Solution 
首先我们知道next数组中next[i]表示的是以第i个字符结尾的前缀中最长公共前后缀的长度，即从s[0]到s[Next[i]-1]与s[i-Next[i]]到s[i-1]这一点的字符串是完全重合的。dp[i]表示表示以i结尾的字符串的所有前缀出现次数之和。那么显然有dp[i]=dp[next[i]]+1,求出dp数组后累加即为答案 
Code

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      const int N=200010;
     
    
   

    

     

    
    

     

      const int mod=10007;
     
    
   

    

     

    
    

     

      char s[N];
     
    
   

    

     

    
    

     

      int next[N],len;
     
    
   

    

     

    
    

     

      void getNext(){
     
    
   

    

     

    
    

     
 int i=0,j=-1;
     
    
   

    

     

    
    

     
 next[0]=-1;
     
    
   

    

     

    
    

     
 while(i<len){
     
    
   

    

     

    
    

     
 if(j==-1||s[i]==s[j]){
     
    
   

    

     

    
    

     

       i++;j++;
     
    
   

    

     

    
    

     
 next[i]=j;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else j=next[j];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 int t,i;
     
    
   

    

     

    
    

     

       scanf("%d",&t);
     
    
   

    

     

    
    

     
 while(t--){
     
    
   

    

     

    
    

     

       scanf("%d",&len);
     
    
   

    

     

    
    

     

       scanf("%s",s);
     
    
   

    

     

    
    

     

       getNext();
     
    
   

    

     

    
    

     
 int res=0,pos;
     
    
   

    

     

    
    

     
 for(i=1;i<=len;i++){
     
    
   

    

     

    
    

     
 pos=i;
     
    
   

    

     

    
    

     
 while(pos){
     
    
   

    

     

    
    

     

       res=(res+1)%mod;
     
    
   

    

     

    
    

     
 pos=next[pos];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",res);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/82790653