对于一个字符集大小为C的字符串P，我们可以将任意两种字符在P中的位置进行互换，例如P=abcba，我们交换a,b就变为bacab，交换a,d就变为dbcbd，交换可以进行任意次。若交换后P变为了字符串Q，则我们称Q与P是匹配的。 现在给定两个字符集大小为C的字符串S,T，请你求出S中有多少个连续子串与T是匹配的。
一个字符串可以这样表示，一个位置首次出现某个字符标为0，否则标为与最近一个该字符位置的差。 于是可以hash了。
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; typedef long long ll; const int maxn=1000000+10,mo1=1000000007,mo2=998244353,jd=1000001; int last[maxn],left[maxn],right[maxn],ans[maxn],a[maxn],b[maxn],mi[maxn][2],sta[80]; int i,j,k,l,t,n,m,p,ca,tot,top,s1,s2,t1,t2; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } void write(int x){ if (!x){ putchar('0'); return; } top=0; while (x){ sta[++top]=x; x/=10; } while (top) putchar('0'+sta[top--]); } int main(){ //freopen("match.in","r",stdin);freopen("match.out","w",stdout); freopen("string.in","r",stdin);freopen("string.out","w",stdout); mi[0][0]=mi[0][1]=1; fo(i,1,1000000){ mi[i][0]=(ll)mi[i-1][0]*jd%mo1; mi[i][1]=(ll)mi[i-1][1]*jd%mo2; } ca=read();p=read(); while (ca--){ n=read();m=read(); fo(i,1,n) a[i]=read(); fo(i,1,m) b[i]=read(); if (n<m){ write(0);putchar('\n');putchar('\n'); continue; } fo(i,1,p) last[i]=0; fo(i,1,n) right[i]=0; fo(i,1,n){ left[i]=last[a[i]]; last[a[i]]=i; } fo(i,1,n) if (left[i]) right[left[i]]=i; fo(i,1,p) last[i]=0; s1=s2=0; fo(i,1,m){ if (!last[b[i]]) t=0;else t=i-last[b[i]]; last[b[i]]=i; s1=((ll)s1*jd%mo1+t)%mo1; s2=((ll)s2*jd%mo2+t)%mo2; } t1=t2=0; fo(i,1,m){ if (!left[i]) t=0;else t=i-left[i]; t1=((ll)t1*jd%mo1+t)%mo1; t2=((ll)t2*jd%mo2+t)%mo2; } tot=0; if (s1==t1&&s2==t2) ans[++tot]=1; fo(i,2,n-m+1){ if (left[i+m-1]<i) t=0;else t=i+m-1-left[i+m-1]; t1=((ll)t1*jd%mo1+t)%mo1; t2=((ll)t2*jd%mo2+t)%mo2; if (right[i-1]&&right[i-1]<=i+m-2){ t=right[i-1]-i+1; j=m-t; (t1-=(ll)mi[j][0]*t%mo1)%=mo1; (t1+=mo1)%=mo1; (t2-=(ll)mi[j][1]*t%mo2)%=mo2; (t2+=mo2)%=mo2; } if (s1==t1&&s2==t2) ans[++tot]=i; } write(tot);putchar('\n'); fo(i,1,tot){ write(ans[i]);putchar(' '); } putchar('\n'); } }