首页 > 代码库 > HDU1711 【kmp算法 基础题】
HDU1711 【kmp算法 基础题】
#include<stdio.h>#include<string.h>int next[10005],lena,lenb;int a[1000005],b[10005];void set_naxt()//子串的next数组{ int i=0,j=-1; next[0]=-1; while(i<lenb) { if(j==-1||b[i]==b[j]) { i++; j++; next[i]=j; } else j=next[j]; }}int kmp(){ int i=0,j=0;//比较时j=0 set_naxt(); while(i<lena) { if(j==-1||a[i]==b[j]) { i++;j++; } else j=next[j];//在这里有可能等于-1, if(j==lenb) return i-j+1; } return -1;}int main(){ int i,t; scanf("%d",&t); while(t--) { memset(next,0,sizeof(next)); scanf("%d%d",&lena,&lenb); for(i=0;i<lena;i++) scanf("%d",&a[i]); for(i=0;i<lenb;i++) scanf("%d",&b[i]); printf("%d\n",kmp()); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。