首页 > 代码库 > vijos 1005
vijos 1005
kmp算法的应用
不懂dev-c++搞什么，某个循环下不去，一直卡在那里....
或许他今天心情不好？明天再试试吧...不浪费时间纠结这个了
这题就是很裸的kmp算法的应用啦...模板题
然后顺便学习了一下如何将数字转成字符串
#include<cstdlib>
itoa(num,a,10)
注意这里的a是字符串或是字符数组，不能是单个字符恩
附上代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<iostream>using namespace std;char s[10000000],p[201];void getnext(char *p,int *next){ int m=strlen(p); next[0]=0;next[1]=0; for(int i=0;i<m;i++){ int j=next[i]; while(j && p[i]!=p[j]) j=p[j]; next[i+1]=(p[i]==p[j]?j+1:0); }}void kmp(char *s,char *p){ int next[201]; getnext(p,next); int n=strlen(s),m=strlen(p); int j=0; for(int i=0;i<n;i++){ while(j && p[j]!=s[i]) j=next[j]; if(p[j]==s[i]) j++; if(j==m){ printf("%d",i-m+1); return; } }}void get(){ int ans=0; char ss[8]; for(int i=1;i<=100000;i++){ itoa(i,ss,10); int l=strlen(ss); for(int j=0;j<l;j++){ s[ans++]=ss[j]; } }}int main(){ cin>>p; get(); kmp(s,p); return 0;}
vijos 1005
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。