首页 > 代码库 > [kmp]HDU1711 Number Sequence
[kmp]HDU1711 Number Sequence
题目大意
题意：给T组数据，每组有长度为n和m的母串和模式串。判断模式串是否是母串的子串，如果是输出最先匹配完成的位置，否则输出-1.
思考
直接套用模板。把char改成int。kmp函数中在模式串遍历到结尾的时候return，若没遍历到结尾，也就是不是子串返回-1
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int nexta[10005],a[1000005],s[10005]; int n,m; void getfail(int* p,int* f){ f[0]=f[1]=0; for(int i=1;i<m;i++) { int j=f[i]; while(j&&p[j]!=p[i]) j=f[j]; f[i+1]=(p[i]==p[j])?j+1:0; }}int kmp(int* t,int* p,int* f){ getfail(p,f); int j=0; for(int i=0;i<n;i++) { while(j&&p[j]!=t[i]) j=f[j]; if(p[j]==t[i]) j++; if(j==m) { return i-j+2; } } return -1;} int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i = 0;i < n; i ++) { scanf("%d",&a[i]); } for(int j = 0; j < m;j ++) { scanf("%d",&s[j]); } printf("%d\n",kmp(a,s,nexta)); } return 0; }
[kmp]HDU1711 Number Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。