2 4
#include <stdio.h> #include <stdlib.h> #include<string.h> #define max 1000000 int m,n; int next[max]; int s1[max],s2[max]; void get_next(int s2[],int next[]) { int i=1; next[1]=0; int j=0; while(i<m) { if(j==0||s2[i]==s1[j]) { i++;j++; next[i]=j; } else j=next[j]; } } void Index_KMP(int n,int m) { int pos=1,j=1,k=0,a; while(pos<=n&&j<=m) { if(j==0||s1[pos]==s2[j]) { pos++;j++; } else j=next[j]; if(j>m) { j=1;k++; if(k==1) { a=pos; } } } if(k==1) { printf("%d %d\n",a-m,a-1); } else printf("-1\n"); } int main() { int n,m,i,j; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&s1[i]); scanf("%d",&m); for(j=1;j<=m;j++) scanf("%d",&s2[j]); get_next(s2,next); Index_KMP(n,m); return 0; }