bzoj4259 残缺的字符串

bzoj4259 残缺的字符串

​​ Description

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。 你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?

Input

第一行包含两个正整数m,n(1<=m<=n<=300000)，分别表示A串和B串的长度。 第二行为一个长度为m的字符串A。 第三行为一个长度为n的字符串B。 两个串均仅由小写字母和号组成，其中号表示相应位置已经残缺。

Output

第一行包含一个整数k，表示B串中可以完全匹配A串的位置个数。 若k>0，则第二行输出k个正整数，从小到大依次输出每个可以匹配的开头位置（下标从1开始）。

Sample Input

3 7 a*b aebr*ob Sample Output

2 1 5 HINT

Source

By Claris

orz fft 字符串匹配 好那么

如果把两个串’*’的部分当成0那么 有如下公式 ∑i(a[i]−b[i])2∗a[i]∗b[i]=0 ∑ i ( a [ i ] − b [ i ] ) 2 ∗ a [ i ] ∗ b [ i ] = 0

#include#include#include#define pi acos(-1)#includeusing namespace std;const int N=300030;struct C{ double r,i; inline friend C operator +(const C &a,const C &b){return (C){a.r+b.r,a.i+b.i};} inline friend C operator -(const C &a,const C &b){return (C){a.r-b.r,a.i-b.i};} inline friend C operator *(const C &a,const C &b){return (C){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};} inline void operator *=(const C &a){*this=*this*a;}}a[N<<2],b[N<<2],c[N<<2];char ss1[N],s2[N];int pend[N],ans,n,m,a1[N<<2],a2[N<<2],R[N<<2];inline void fft(C *x,int f){ for (int i=0;i>1]>>1)|(i&1)<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。