BZOJ4641 基因改造[KMP]

这道题以前好像模拟的时候做过，当时不会做，于是用hash水过去了。。

正解是KMP，还是用当前字符与上一次相同字符位置的距离表示数组，于是数值相等时就代表相似。第一次出现用INF代替。

然后要匹配有多少个。暴力匹配的话是：匹配到$s_i,t_{j+1}$时，若$s_i=t_{j+1}$或者是$s_i>j$且$t_{j+1}>j$。这表示距离相同或者第一次出现时的匹配。

注意第一次出现的判断：因为从$s$串某一处开始，后面有的字符的距离值不是INF但与之相聚$d$的字符却不在匹配串范围内。

这就要求有上面那个条件。

于是KMP匹配，匹配成功一个字符的条件也就是上面那个。当我失配的时候，也保证是对的说。不太会讲，可以自己yy。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e6+,INF=+;

 int pres[N],pret[N],slas[N],tlas[N];

 int nxt[N],ans[N],cnt;

 int T,C,m,n;

 int main(){//freopen("5.in","r",stdin);freopen("5.ans","w",stdout);

     read(T),read(C);while(T--){

         read(n),read(m);

         memset(slas,,sizeof slas),memset(tlas,,sizeof tlas);cnt=;

         for(register int i=,x;i<=n;++i)read(x),pres[i]=slas[x]?i-slas[x]:INF,slas[x]=i;

         for(register int i=,x;i<=m;++i)read(x),pret[i]=tlas[x]?i-tlas[x]:INF,tlas[x]=i;

         nxt[]=;int j=;pret[m+]=,pres[n+]=;

         for(register int i=;i<=m;++i){

             while(j&&!(pret[j+]==pret[i]||pret[i]>j&&pret[j+]>j))j=nxt[j];

             nxt[i]=(pret[j+]==pret[i]||pret[i]>j&&pret[j+]>j)?++j:;

         }

         j=;

         for(register int i=;i<=n;++i){//dbg(i),dbg(j);

             while(j&&!(pres[i]==pret[j+]||pret[j+]>j&&pres[i]>j))j=nxt[j];

             (pres[i]==pret[j+]||pret[j+]>j&&pres[i]>j)&&(++j);

             if(j==m)ans[++cnt]=i-j+;

         }

         printf("%d\n",cnt);

         for(register int i=;i<=cnt;++i)printf("%d ",ans[i]);

         puts("");

     }

     return ;

 }

巴特西

BZOJ4641 基因改造[KMP]

最新文章

热门文章