两道水kmp-求next数组

本文主要是介绍两道水kmp-求next数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    kmp的讲解：http://blog.csdn.net/u013076044/article/details/41833325

   next数组的详细讲解：http://blog.csdn.net/yearn520/article/details/6729426

   

        这两道题就是套一下模板：

       poj1961&poj 2406

     

/×poj1961×/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace  std;int next[1000010];
char s[1001000];
void getnext(){int len = strlen(s);next[0]=0;for(int i=1;i<len;i++){int k=next[i-1];while(k!=0&&s[k]!=s[i])k=next[k-1];if(s[k]==s[i])next[i]=k+1;elsenext[i]=0;}
}int main (){int  n;int cas =0;while(scanf("%d",&n)==1){if(n==0) break;cin>>s;getnext();printf("Test case #%d\n",++cas);for(int i=2;i<=n;i++){if(i%(i-next[i-1])==0){int ans=i/(i-next[i-1]);if(ans>1){printf("%d %d\n",i,ans);}}}puts("");}
}

/×2406×/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace  std;int next[1000010];
char s[1001000];
void getnext(){int len = strlen(s);next[0]=0;for(int i=1;i<len;i++){int k=next[i-1];while(k!=0&&s[k]!=s[i])k=next[k-1];if(s[k]==s[i])next[i]=k+1;elsenext[i]=0;}
}int main (){int  n;int cas =0;while(cin>>s){if(s[0]=='.')break;int n=strlen(s);getnext();int ans=n/(n-next[n-1]);printf("%d",(n%(n-next[n-1])==0)?ans:1);puts("");}
}

  

这篇关于两道水kmp-求next数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---