传送门
题解：
我的做法感觉算好写的。
假设在 0 0 0位置上出现了所有字符，那么对于每个串记录每个位置的字符上一次出现位置距离这个位置有多远，然后匹配的时候直接比较上一次出现的位置，注意比较的时候需要取min防止越界。
代码：
#include<bits/stdc++.h> #define ll long long #define re register #define gc get_char #define cs const namespace IO{inline char get_char(){static cs int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2;return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}template<typename T>inline T get(){char c;T num;while(!isdigit(c=gc()));num=c^48;while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);return num;}inline int gi(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; cs int N=1e6+7; int n,m; int a[N],b[N]; int las[N],nxt[N]; int ans[N],tot; signed main(){ #ifdef zxyoifreopen("DNA.in","r",stdin); #endifint T=gi();int C=gi();while(T--){n=gi(),m=gi();tot=0;memset(las,0,sizeof las);for(int re i=1;i<=n;++i){int v=gi();a[i]=i-las[v];las[v]=i;}memset(las,0,sizeof las);for(int re i=1;i<=m;++i){int v=gi();b[i]=i-las[v];las[v]=i;}for(int re i=2,j=0;i<=m;++i){while(j){int l1=std::min(b[i],j+1),l2=b[j+1];if(l1==l2)break;j=nxt[j];}++j;nxt[i]=j;}for(int re i=1,j=0;i<=n;++i){while(j){int l1=std::min(a[i],j+1),l2=b[j+1];if(l1==l2)break;j=nxt[j];}++j;if(j==m)ans[++tot]=i-m+1,j=nxt[j];}printf("%dn",tot);for(int re i=1;i<=tot;++i)printf("%d ",ans[i]);puts("");}return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
