对题目中的数列进行一些变形，每个数的值变为其下标减去这个数上一次出现的下标，这样如果不考虑每个数的第一次出现，就是普通的字符串匹配，而一个数第一次出现相当于一个限制条件：与他匹配的数必须大于等于他在模式串里的下标，而我们在kmp的时候直接判这个就可以了
但是我们知道两个串那题是不能KMP的，为什么这题就能KMP呢？能KMP的充要条件是如果一个串能和next数组指向的后缀匹配，那么一定能和前缀匹配，而两个串那题不满足这个性质，但是这道题的限制条件满足这个性质，分类讨论一下就能证了（在求next数组的时候两个第一次出现的数是能匹配的）
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<ctime> #include<algorithm> #include<iomanip> #include<cmath> #include<vector> #include<set> #include<bitset> #include<queue> #include<stack> #include<map> using namespace std; #define MAXN 1000010 #define MAXM 1010 #define eps 1e-8 #define ll long long #define INF 1000000000 #define MOD 1000000007 int a[MAXN],b[MAXN]; int n,m; int tai[MAXN]; int ans[MAXN],tot; int nxt[MAXN]; bool ck(int x,int y){ if(b[x]==-1){ if(y>=x||y==-1){ return 1; } } return b[x]==y; } int main(){ int i,j; int tmp; scanf("%d%*d",&tmp); while(tmp--){ scanf("%d%d",&n,&m); memset(tai,0,sizeof(tai)); for(i=1;i<=n;i++){ scanf("%d",&a[i]); int t=tai[a[i]]; tai[a[i]]=i; a[i]=i-t; } memset(tai,0,sizeof(tai)); for(i=1;i<=m;i++){ scanf("%d",&b[i]); int t=tai[b[i]]; tai[b[i]]=i; if(!t){ b[i]=-1; }else{ b[i]=i-t; } } j=0; tot=0; for(i=2;i<=m;i++){ while(j&&!ck(j+1,b[i])){ j=nxt[j]; } if(ck(j+1,b[i])){ j++; } nxt[i]=j; } j=0; for(i=1;i<=n;i++){ while(j&&!ck(j+1,a[i])){ j=nxt[j]; } if(ck(j+1,a[i])){ j++; } if(j==m){ ans[++tot]=i-m+1; j=nxt[j]; } } printf("%d\n",tot); for(i=1;i<=tot;i++){ printf("%d ",ans[i]); } printf("\n"); } return 0; } /* 3 3 6 3 1 2 1 2 3 2 3 1 3 6 3 1 2 1 2 1 2 3 1 3 6 3 1 1 2 1 2 1 3 1 3 */
