题目大意:
还是kmp魔板题,给你两串数,从一串中找出另一串,要是存在多个,就输出最先找到的位置。
代码:
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
int a[1000500];
int c[10050];
int m,n;
int my_next[10050];
void get_my_next()
{
int i=0,k=-1;
my_next[0]=-1;
while(i<m)
{
if(k!=-1&&c[i]!=c[k])
{
k=my_next[k];
continue;
}
i++;k++;
if(c[i]==c[k])my_next[i]=my_next[k];
else my_next[i]=k;
}
}
int my_kmp()
{
int i=0,j=0;
while(i<n)
{
if(j==-1||a[i]==c[j])
{
i++;j++;
}
else
{
j=my_next[j];
}
if(j==m)
{
return i-m+1;
}
}
return -1;
}
int main()
{
int test;
cin>>test;
while(test--)
{
scanf("%d",&n);
scanf("%d",&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++)
{
scanf("%d",&c[i]);
}
get_my_next();
cout<<my_kmp()<<endl;
}
}