hdu 4513 KMP里next数组的运用
这道题不难 前提是搞懂next数组的求的过程 加上点递归的思想
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; char str[200021]; int main() { int n,i,j,T; int next[200020]; scanf("%d",&T); while(T--) { scanf("%d",&n); scanf("%s",str); str[n]=‘@‘; n++; memset(next,0,sizeof(next)); next[0]=-1; int sum=0,j=0,k=-1; while(j<n) { if(k==-1||str[j]==str[k]) { ++k; ++j; next[j]=k; } else k=next[k]; } sum=0; for(i=1;i<n;i++) { sum++; int k=i; while(next[k]) { sum++; sum%=10007; k=next[k]; } } printf("%d\n",sum); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。