题面

大致题意：

给定两个数列A，B，长度分别为N和M

求出 满足 Ak=B1 ,Ak+1=B2......Ak+M-1=Bm

的最小k值

如果有多个k值输出最小的一个

题解

KMP裸题

直接计算B数列的next值KMP匹配即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 1000100int nt[MAX],A[MAX],B[MAX],N,M;inline int read(){ register int x=0,t=1; register char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-'){t=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*t;}void GetNext(){ nt[1]=0; for(int i=2;i<=M;++i) { int t=nt[i-1]; while(B[t+1]!=B[i]&&t) t=nt[t-1]; if(t==0) { if(B[1]==B[i]) nt[i]=1; else nt[i]=0; } else nt[i]=t+1; }}int KMP(){ int i=1,j=1; while(j<=N) { if(B[i]==A[j]) { ++i;++j; } else { if(i==1)j++; else i=nt[i-1]+1; } if(i>M) return j-M; } return -1;}int main(){ int T=read(); while(T--) { N=read();M=read(); for(int i=1;i<=N;++i) A[i]=read(); for(int j=1;j<=M;++j) B[j]=read(); GetNext(); printf("%d\n",KMP()); } return 0;}