首页分享【BZOJ4641】—基因改造（Kmp）

【BZOJ4641】—基因改造（Kmp）

来源：花匠小妙招时间：2025-01-04 07:20

传送门
b z o j bzoj bzoj关了,干脆别开了，只有 d a r k b z o j darkbzoj darkbzoj了

这道题和这道有区别？？？

#include<bits/stdc++.h> using namespace std; const int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ob==ib)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } #define ll long long #define re register #define pii pair<int,int> #define fi first #define se second #define pb push_back #define cs const #define bg begin #define poly vector<int> #define chemx(a,b) ((a)<(b)?(a)=(b):0) #define chemn(a,b) ((a)>(b)?(a)=(b):0) cs int N=1000005; int fail[N],T,c,last[N]; int a[N],b[N],v[N],n,m,ans[N],tot; inline bool comp(int a,int b,int l){return (a==b)||(a>l&&b>l); } int main(){T=read(),c=read();while(T--){n=read(),m=read(),tot=0;for(int i=1;i<=n;i++)v[i]=read();memset(last,0,sizeof(int)*(c+1));for(int i=1;i<=n;i++)a[i]=i-last[v[i]],last[v[i]]=i;for(int i=1;i<=m;i++)v[i]=read();memset(last,0,sizeof(int)*(c+1));for(int i=1;i<=m;i++)b[i]=i-last[v[i]],last[v[i]]=i;for(int i=0,j=2;j<=m;j++){while(i&&!comp(b[i+1],b[j],i))i=fail[i];if(comp(b[i+1],b[j],i))i++;fail[j]=i;}for(int i=0,j=1;j<=n;j++){while(i&&!comp(b[i+1],a[j],i))i=fail[i];if(comp(b[i+1],a[j],i))i++;if(i==m)ans[++tot]=j-i+1,i=fail[i];}cout<<tot<<'n';for(int i=1;i<=tot;i++)cout<<ans[i]<<" ";puts("");} }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556