以下不是KMP算法——
以下是kiki告诉我的方法，好厉害的思维——
就是巧用标记，先标记第一个出现的所有位置，然后一遍遍从标记的位置往下找。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int xin,t,i,j,n,ans,id,xiabiao[200010],shunxu; char ch[200010]; scanf("%d",&t); while(t--) { memset(xiabiao,0,sizeof(xiabiao)); scanf("%d",&n); scanf("%s",ch); id=0;shunxu=0; ans=0; for(j=0;j<n;j++) { if(ch[j]==ch[shunxu]) xiabiao[id++]=j; } ans+=id; ans=ans%10007; do { shunxu++; xin=0; for(i=0;i<id;i++) { if(xiabiao[i]+1<n) { if(ch[xiabiao[i]+1]==ch[shunxu]) { xiabiao[xin++]=xiabiao[i]+1; } } } ans+=xin; ans=ans%10007; id=xin; }while(shunxu<n-1); printf("%d\n",ans); } return 0; }