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;
}

?