- #include
- #include
- #include
- using namespace std;
- intlen1,len2,a[1000005],b[10005],ne[10005];
- void getnext()
- {
- int i,j;
- ne[0]=0;ne[1]=0;
- for(i=1;i)
- {
- j=ne[i];
- while(j&&b[i]!=b[j])j=ne[j];
- if(b[i]==b[j])ne[i+1]=j+1;
- elsene[i+1]=0;
- }
- }
- void kmp()
- {
- inti,j=0;
- intflag=0;
- for(i=0;i)
- {
- while(j&&a[i]!=b[j])j=ne[j];
- if(a[i]==b[j])j++;
- if(j==len2)
- {
- flag=1;
- printf("%d\n",i-len2+2);
- break;
- }
- }
- if(!flag)cout<<-1;
- }
- int main()
- {
- int T,i;
- cin>>T;
- while(T--)
- {
- cin>>len1>>len2;
- for(i=0;i>a[i];
- for(i=0;i>b[i];
- getnext();
- kmp();
- }
- return 0;
- }
来源: