hdu 3336 KMP之杭电next魂魄

hdu 3336 KMP之杭电next灵魂
Problem DescriptionInputOutputSample Input/*本题题意可以理解为 把串a的各个子串分别作为模式串 查找模式串在主串中出现的次数我们可以把串a的next函数打印出来 然后对应子串的next也就是next函数中的一部分所以就不用一个一个子串的去求子串的next函数了 另外 我们可以发现当某个子串只在a中出现一次的时候 再往子串上加字符 即下个子串也一定是1如aabcde aabc在主串中出现一次 那aabcd肯定更加是1次所以之后的全是1 就没必要继续调用KMP了 就可以节省很多时间 防止超时*/#include<stdio.h>#include<string.h>char a[200005];char b[200005];int next[200005],d,d2,cnt;void get_next(){ int i=1,j=0; next[1]=0; while(i<=d) { if(j==0||a[i]==a[j]) {i++;j++;next[i]=j;} else j=next[j]; }}int KMP(char *str){ int i=1,j=1; while(i<=d) { if(j==0||b[j]==a[i]) { i++;j++; if(j==d2+1) {cnt++; j=1;} } else j=next[j]; } return cnt;}int main(){ int t,i,ans,k; scanf("%d",&t); while(t--) { ans=0; scanf("%d",&d); getchar(); gets(a+1); get_next(); // for(i=1;i<=d;i++) // printf("%d ",next[i+1]-1); // printf("\n"); d2=0; for(i=1;i<=d;i++) { cnt=0; b[i]=a[i]; b[i+1]='\0'; d2++; k=KMP(&b[1]); // printf("%d ",k); if(ans>10007) ans=ans%10007; else ans=ans+k; if(k==1) { ans=(ans+(d-i))%10007; break; } } printf("%d\n",ans); } return 0;}