- #include
- #include
- #include
- #include
- using namespace std;
- intn[10005];
- ints[1000005],a[10005];
- int len1,len2;
- void kmp()
- {
- n[0]=0;
- for(inti=1,k=0;i)
- {
- while(k>0&&a[k]!=a[i]) k=n[k-1];
- if(a[k]==a[i]) k++;
- n[i]=k;
- }
- }
- int main()
- {
- ///cout << "Hello world!" << endl;
- int T;cin>>T;
- while(T--)
- {
- scanf("%d%d",&len1,&len2);
- for(inti=0;i)
- scanf("%d",&s[i]);
- for(inti=0;i)
- scanf("%d",&a[i]);
- kmp();
- intflag=-1;
- for(inti=0,j=0;i)
- {
- while(j>0&&a[j]!=s[i]) j=n[j-1];
- if(a[j]==s[i]) j++;
- if(j==len2) { flag=i-len2+1;break; }
- }
- if(flag>=0) printf("%d\n",flag+1);
- elseputs("-1");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2084555.html