hdu 1711 KMP模版题 冷不防 2022-07-26 05:23 111阅读 0赞 [点击打开链接][Link 1] 题意: 找模式串在文本串中首次出现的位置; 分析:, 数据量比较大, 因此要用KMP来解决,套上KMP模版就行了; #include<bitset> #include<map> #include<vector> #include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<stack> #include<queue> #include<set> #define inf 0x3f3f3f3f #define mem(a,x) memset(a,x,sizeof(a)) #define F first #define S second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; inline int in() { int res=0;char c;int f=1; while((c=getchar())<'0' || c>'9')if(c=='-')f=-1; while(c>='0' && c<='9')res=res*10+c-'0',c=getchar(); return res*f; } const int N=1000110; int Next[10010]; int a[N],b[N/10]; int main() { int T=in(); while(T--) { int n=in(),m=in(); for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<m;i++) scanf("%d",b+i); int k=-1,j=0; Next[0]=-1; while(j<m) { if(k==-1 || b[k]==b[j]) Next[++j]=++k; else k=Next[k]; } int i=0; j=0; while(i<n && j<m) { if(j==-1 || a[i]==b[j]) i++,j++; else j=Next[j]; } if(j==m) printf("%d\n",i-j+1); else puts("-1"); } return 0; } [Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1711
还没有评论，来说两句吧...