题意：对于长度为len的字符串，我们知道它包含有len个前缀，，现在要你统计出这个字符串里面，包含这些前缀的总个数。
思路：这题可以运用KMP的next数组来解，不过也太难想了吧orz，为了用next解这题想那么多也不算是很好的方法orz。
再对这两个串的last’进行相同的步骤，直到next[last”””]=0为止。
现在漏下的解就是原串中间部分以last作结的和其他字母作结的子串，所以从1到len个字符依次做相同的处理就可以找出所有的解了，这是动态规划的思想。
先附上简单一点的没经过其他处理的代码来源：
#include <cstdio>#include <cstring>int const MAX = 1e8;int const MOD = 10007;int next[MAX];char s[MAX];void get_next(){int i = 0, j = -1;next[0] = -1;while(s[i] != '\0'){if(j == – 1 || s[i] == s[j]){i++;j++;next[i] = j;}elsej = next[j];}}int main(){int T, len, ans;scanf("%d", &T);while(T–){memset(next, 0, sizeof(next));scanf("%d %s", &len, s);get_next();ans = len;for(int i = 1; i <= len; i++){int tmp = next[i];while(tmp){ans = (ans + 1) % MOD;tmp = next[tmp];}}printf("%d\n", ans);}}每次从next[last]回溯到next[last””]=0也是比较麻烦，直接记录下next[last’]的解就不需要回溯了。//2864 KB78 ms#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define mod 10007using namespace std;char str[201000];int next[201000],dp[201000];int len;void getnext(){int j=next[0]=-1;int i=0;while(i<len){while(j>-1&&str[i]!=str[j])j=next[j];i++;j++;next[i]=j;}}int main(){int cas;scanf("%d",&cas);while(cas–){int ans=0;scanf("%d",&len);scanf("%s",str);getnext();for(int i=1;i<=len;i++){dp[i]=dp[next[i] ]+1;dp[i]%=mod;ans+=dp[i];ans%=mod;}printf("%d\n",ans);}return 0;}
第二个方法蛮好的，dp，dp[i]表示原串中的以（1…n）为前缀出现的次数，所以dp[i+1]在（1…n）匹配成功的基础上如果能使str[next of pos]=str[i+1],那么dp[i+1]匹配成功。
所以每次匹配成功要记录匹配成功的位置用栈记录即可。
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define mod 10007using namespace std;char str[201000];int Stack[201000];int main(){int cas;scanf("%d",&cas);while(cas–){int ans=0,len,top=0;memset(Stack,-1,sizeof(Stack));scanf("%d",&len);scanf("%s",str);for(int j=0;j<len;j++)if(str[j]==str[0]){Stack[top++]=j;ans++;}ans%=mod;for(int i=1;i<len;i++){top=0;for(int j=0;~Stack[j];j++){if(str[i]==str[Stack[j]+1]){Stack[top++]=Stack[j]+1;ans++;}}ans%=mod;Stack[top]=-1;}printf("%d\n",ans);}return 0;}
你可以很有个性，但某些时候请收敛。
