发现是对 \(A\) 的字串映射到 \(B\)，求有多少的字串满足这种映射为双射。、
直接求比较困难，但是发现这个只是跟相对位置有关的一个值，那我们将一个点的值改成与上一个出现相同数值的下标的差值，第一个出现的值就可以直接把值设为它的下标，这样就可以很好的避免时间复杂度太大的问题。之后可以对每一个区间求 hash 值，每更新区间时把一个点的权值修改，时间复杂度可以达到 \(O(n)\) ，当然可以无脑数据结构，时间复杂度 \(O(n \log n)\)。也可以使用 KMP ，但是在匹配的时候需要注意，若匹配串枚举到的点的值比现在的匹配长度还长，那就跳过，因为这个点匹配的话是需要更改值的。
#include<bits/stdc++.h>
using namespace std;
const int N=1E6+6,base=1331;
int T,C,n,m;
int a[N],b[N],c[N];
int aa[N],bb[N];
int lst[N],nxt[N];
int d[N];
int f[N],tot,ans[N];
signed main() {scanf("%d%d",&T,&C);while(T--) {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)scanf("%d",a+i);for(int i=1; i<=m; i++)scanf("%d",b+i);memset(d,0,sizeof d);for(int i=1; i<=m; i++) {bb[i]=i-d[b[i]];d[b[i]]=i;// cout<<bb[i]<<endl;}bb[m+1]=0;memset(d,0,sizeof d);for(int i=1; i<=n; i++) {aa[i]=i-d[a[i]];//cout<<aa[i]<<endl;d[a[i]]=i;}aa[n+1]=0;f[0]=-1;for(int i=2,j=0; i<=m; i++) {while(~j && !(bb[i] == bb[j + 1] || (bb[i] > j && bb[j + 1] > j)))j=f[j];f[i]=++j;// cout<<j<<endl;}tot=0;for(int i=1,j=0; i<=n; i++) {while(~j && (aa[i] != bb[j + 1] && (aa[i] <= j || bb[j + 1] <= j)))j=f[j];++j;if(j==m)ans[++tot]=i-m+1; // cout<<j<<endl;}cout<<tot<<endl;for(int i=1;i<=tot;i++){cout<<ans[i]<<" ";}puts("");}return 0;
}