// Manacher算法，很好用。 char s[*N]; //储存临时串
int save[*N];//中间记录 int Manacher(char tmp[])
{
int len=strlen(tmp);
int cnt=;
for(int i=;i<len;i++)
{
s[cnt++]='#';
s[cnt++]=tmp[i];
}
s[cnt++]='#';
memset(save,,sizeof(save));
int a=,p=;
int mx=;
for(int i=;i<cnt-;i++)
{
if(i>=p)
{
int num=;
while(i+num<cnt&&i-num>=&&s[i+num]==s[i-num])
{
num++;
}
p=i+num-; //能到达的最远位置
a=i;
save[i]=num-; //从这个位置出发最长的回文
if(save[i]==) continue;
if(s[i]=='#')
{
if(*((save[i]-)/ +)>mx) mx=*((save[i]-)/+);
}
else
{
if(*(save[i]/)+>mx) mx=*(save[i]/)+;
}
}
else
{
int j=*a-i;
if( i+save[j] < p)
{
save[i]=save[j];
if(save[i]==) continue;
if(s[i]=='#')
{
if(*((save[i]-)/ +)>mx) mx=*((save[i]-)/+);
}
else
{
if(*(save[i]/)+>mx) mx=*(save[i]/)+;
}
}
else
{
int k=*i-p;
while(p+<cnt&&k->=&&s[p+]==s[k-])
{
p++;
k--;
}
a=i;
save[i]=p-i;
if(save[i]==) continue;
if(s[i]=='#')
{
if(*((save[i]-)/ +)>mx) mx=*((save[i]-)/+);
}
else
{
if(*(save[i]/)+>mx) mx=*(save[i]/)+;
}
}
}
}
return mx;
}
kmp，扩展kmp
// 感觉kmp可以理解。 #define N 100010
int s[N];
int next[N];
int t[N]; int main()
{
//freopen("//home//chen//Desktop//ACM//in.text","r",stdin);
//freopen("//home//chen//Desktop//ACM//out.text","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%d",s+i);
for(int i=;i<m;i++)
scanf("%d",t+i);
///////////////求next
int j=;
next[]=;
for(int i=;i<m;i++)
{
while(j!=&&t[j]!=t[i]) j=next[j-];
if(t[j]==t[i]) j++;
next[i]=j;
} ///////////////////// j=;
int ans=-;
for(int i=;i<n;i++)
{
while(j!=&&s[i]!=t[j]) j=next[j-];
if(s[i]==t[j]) j++;
if(j==m)
{
ans=i+-m+;
break;
}
} ///////////////////
if(ans==-)
printf("-1\n");
else
printf("%d\n",ans);
}
return ;
} // 扩展kmp。
#defien N int next[N],sum[N];// sum用来记录 void build(char s[])
{
memset(next,,sizeof(next));
int p=,a=;
next[]=len;
for(int i=;i<len;i++)
{
if(i+next[i-a]-<p)
{
next[i]=next[i-a];
}
else
{
int k=p-i;
while(p+<len && s[p+]==s[k+])
{
p++; k++;
}
p=max(p,i);
next[i]=k+;
a=i;
}
}
} void extend_kmp(char s[],char t[])//求从s到t上的最大前缀
{
memset(sum,,sizeof(sum));
int p=-,a=;
for(int i=;i<len;i++)
{
if(i+next[i-a]-<p)
{
sum[i]=next[i-a];
}
else
{
int k=p-i;
while(p+<len && s[p+]==t[k+])
{
p++; k++;
}
p=max(p,i);
sum[i]=k+;
a=i;
}
}
}
最小表示法
int mistr(char s[],int len) //输入一串字符，返回最小表示法的起始位置
{
int i=,j=,k=;
while(i<len&&j<len&&k<len)
{
if(s[i+k]==s[j+k])
{
k++;
}
else
{
if(s[i+k] > s[j+k]) i=i+k+;
if(s[i+k] < s[j+k]) j=j+k+;
k=;
if(i==j) j++;
}
}
return min(i,j);
}