222
查看原帖
222
1339404
zenglicheng666楼主2024/6/23 11:53
#include<bits/stdc++.h>
//~ #define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define mid ((l+r)>>1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
using namespace std;
const int N=1e5+5,Mod=998244353;
//typedef __int128_t i128;
//i128 _base=1;
//inline int mol(int x){return x-Mod*(_base*x>>64);}
//inline void Add(int &x,int y){x=mol(x+y+Mod);}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
int n,m,q,p[N];
int a[N],b[N];
int s[N],t[N];
int e[N][26];
inline void KMP(int x,int y){
    int j=0;
    For(i,1,m) p[i]=0;
    p[1]=0;
    for(int i=2;i<=m;++i){
        while(j>0&&t[j+1]!=t[i])j=p[j];
        if(t[i]==t[j+1])++j;
		p[i]=j;
    }
    j=0;
    for(int i=1;i<=n;++i){
        while(j>0&&t[j+1]!=s[i])
			j=p[j];
        if(t[j+1]==s[i])
			++j;
        if(j==m){
            e[i-m+1][x]=y;
			j=p[j];
		}
    }
}
int qzh[N][26];
int ans[N],tot;
signed main(){
	//_base=(_base<<64)/Mod;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
    n=read(),m=read();
    q=read();
    For(i,1,n) a[i]=read();
    For(i,1,n){
        For(j,1,q) qzh[i][j]=qzh[i-1][j];
        qzh[i][a[i]]++;
    }
    For(i,1,m) b[i]=read();
    For(i,1,q){
		bool bk=0;
        For(k,1,n){
            if(a[k]==i) s[k]=1,bk=1;
            else s[k]=0;
        }
        if(!bk) continue;
        For(j,1,q){
			bk=0;
            For(k,1,m){
                if(b[k]==j) t[k]=1,bk=1;
                else t[k]=0;
            }
            if(!bk) continue;
            KMP(i,j);
        }
    }
    For(i,1,n){
		bool flag=0;
		For(t,1,q){
			if(qzh[i+m-1][t]-qzh[i-1][t]>0&&!e[i][t]){
				flag=1;
				break;
			}
		}
		if(flag) continue;
		int p=0;flag=0;
		For(t,1,q){
			if(qzh[i+m-1][t]-qzh[i-1][t]==0) continue;
			int minx=e[i][t];
			if(p>=minx||!e[i][t]){flag=1;break;}
			p=minx;
		}
		if(!flag) ans[++tot]=i;
    }
    printf("%d\n",tot);
    For(i,1,tot) printf("%d\n",ans[i]); 
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

2024/6/23 11:53
加载中...