转载的解析
题目来源
#include<stdio.h> #include<stdlib.h> #include<string.h> int a[1000001]; int b[1000001]; int next[1000001]; int main() { int n; scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); int m; scanf("%d",&m); for(int i=1; i<=m; i++) scanf("%d",&b[i]); next[1]=0; for(int i=2; i<=m; i++) { int j; j=next[i-1]; while(j&&b[j]!=b[i-1]) { j=next[j]; } next[i]=j+1; } int s1=1; int s2=1; int num=0; int ans=0; while(s1<=n&&s2<=m) { if(s2==0||a[s1]==b[s2]) { s1++; s2++; if(s2>m) { num++; if(num==1) ans=s1-s2+1; s1=s1-s2+1+1; s2=1; } } else { s2=next[s2]; } } if(num==1) printf("%d %d\n",ans,ans-1+m); else printf("-1\n"); return 0; } /*************************************************** User name: 18bk15薛文慧 Result: Accepted Take time: 160ms Take Memory: 772KB Submit time: 2019-10-01 15:39:30 ****************************************************/