HDu 3336:Count the string(データ構造、シリアル、KMPアルゴリズム)

Count the string
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3797    Accepted Submission(s): 1776
Problem Description
It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:
s: "abab"
The prefixes are: "a", "ab", "aba", "abab"
For each prefix, we can count the times it matches in s. So we can see that prefix "a"matches twice, "ab"matches twice too, "aba"matches once, and "abab"matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For "abab", it is 2 + 2 + 1 + 1 = 6.
The answer may be very large, so output the answer mod 10007.
 
 
Input
The first line is a single integer T, indicating the number of test cases.
For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.
 
 
Output
For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.
 
 
Sample Input
1
4
abab
 
 
Sample Output
6
 
 
Author
foreverlin@HNU
 
 
Source
HDOJ Monthly Contest – 2010.03.06
 
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  
1711  
1686  
3746  
1358  
3341  
 
データ構造:シリアル:KMPアルゴリズム.
KMPアルゴリズムの実装をあまり見ていないし、他の人のコードを見ても分かるようで分からないので、とにかく最後に参考にして変更したのはACです.
KMPアルゴリズムは2つのステップに分けられる:1、next[]配列を生成する.2、KMP処理.
この問題は、next[]を生成する関数を最初のステップで変更するだけで、結果を得ることができます.
はっきりしていないので,また見る時間がある.
 

 1 #include <iostream>

 2 #include <string.h>

 3 using namespace std;  4 char s[200001];  5 int next[200001];  6 int c[200001];  7 int ans;  8 void GetNext(char t[],int next[])  9 { 10     memset(c,0,sizeof(c)); 11     int j,k; 12     j=0;k=-1;next[0] = -1; 13     int length; 14     for(length = 0;t[length]!='\0';length++); 15     while(j<length){ 16         if(k==-1 || t[j]==t[k]){ 17             if(k!=-1){ 18                 c[j] = c[k] + 1; 19                 ans+=c[j]; 20  } 21             j++;k++; 22             next[j] = k; 23  } 24         else

25             k = next[k]; 26  } 27 } 28 int main() 29 { 30     int T,n; 31     cin>>T; 32     while(T--){ 33         cin>>n; 34         cin>>s; 35         ans = 0; 36  GetNext(s,next); 37         cout<<(ans+n)%10007<<endl; 38  } 39     return 0; 40 }

 
 
もう一度この問題をやり直して、今度はKMPアルゴリズムがどうなっているのか大体分かりましたが、この問題のDP部分はまだよく分かりません.
DP式はdp[j]=dp[next[j]+1である.以前のj文字が接頭辞であった文字列が総文字列に現れる回数−1を表す.
コード:
 

 1 #include <iostream>

 2 

 3 using namespace std;  4 char a[200001];  5 int next[200001];  6 int dp[200001];  7 int n,ans;  8 void GetNext(void)  //KMP      

 9 { 10     int j=0,k=-1; 11     next[0] = -1; 12     while(j<n){ 13         if(k==-1){ 14             j++;k++; 15             next[j] = 0; 16  } 17         else if(a[j]==a[k]){ 18             dp[j] = dp[k] + 1;  //DP  

19             ans += dp[j];       //    

20             next[j+1] = k + 1; 21             j++; 22             k = next[j]; 23  } 24         else

25             k = next[k]; 26  } 27 } 28 int main() 29 { 30     int T; 31     cin>>T; 32     while(T--){ 33         cin>>n; 34         cin>>a; 35         ans = 0; 36  GetNext(); 37         cout<<(ans+n)%10007<<endl; 38  } 39     return 0; 40 }

 
 
Freecode : www.cnblogs.com/yym2013