[BZOJ4503]两个串 – FFT

Description

兔子们在玩两个串的游戏。给定两个字符串S和T,兔子们想知道T在S中出现了几次,分别在哪些位置出现。注意T中可能有“?”字符,这个字符可以匹配任何字符。


Input

两行两个字符串,分别代表S和T。
S长度不超过1e5,T长度不会超过S。S中只包含小写字母,T中只包含小写字母和“?”


Output

第一行一个正整数k,表示T在S中出现了几次。
接下来k行正整数,分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出,S下标从0开始。


Solution

分情况讨论:
如果没有”?”,考虑两个串匹配的条件:

如果有”?”,无论是否等于都不影响结果
于是,将”?”的权值定为0,当下面式子的bool值为1时,两串匹配

翻转b数组求a和b的卷积g判断下g(l1)到g(l2)区间经过运算后0的个数


Code

#include<set>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 400100
#define pi acos(-1)
#define ll long long
#define lowbit(x) (x&-x)
#define maxint 2147483647
#define abs(x) (a<0?-a:a)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ckmax(a,b) (a=max(a,b))
#define ckmin(a,b) (a=min(a,b))
#define isd(c) ('0'<=c&&c<='9')
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c='\0'){char ch[(sizeof(T)+1)<<1];if (x<0) putchar('-'),x=-x;
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!='\0') putchar(c);
}
struct cpx {double a,b;cpx(){}
    cpx(double x, double y) {a=x;b=y;}
    inline cpx operator*(const cpx&x)const {return cpx(a*x.a-b*x.b,a*x.b+b*x.a);}
    inline cpx operator*=(const cpx&x) {return*this=*this*x;}
    inline cpx operator+(const cpx&x)const {return cpx(a+x.a,b+x.b);}
    inline cpx operator-(const cpx&x)const {return cpx(a-x.a,b-x.b);}
}a[N],b[N],c[N],d[N];
int l,r[N],lim=1,n,m,l1,l2;
char s1[N],s2[N];
ll numa[N],numb[N],powa[N],powb[N],sta[N],top=0,sm=0,ans=0;
inline void fft(cpx*a,int t){
    for (int i=0;i<lim;++i)if (i<r[i])swap(a[i],a[r[i]]);
    for (int i=1;i<lim;i<<=1){
        cpx s(cos(pi/i),t*sin(pi/i));int tmp=i<<1;
        for (int j=0;j<lim;j+=tmp){
            cpx w(1,0);
            for (int k=0;k<i;++k){
                cpx x=a[j+k],y=w*a[i+j+k];
                a[j+k]=x+y,a[j+k+i]=x-y,w*=s;
            }
        }
    }
}
inline void work(){
    for (int i=0;i<=l1;++i){
        numa[i]=s1[i]-'a'+1,powa[i]=numa[i]*numa[i];
        a[i].a=numa[i],c[i].a=powa[i];
    }
    for (int i=0;i<=l2;++i){
        numb[l2-i]=s2[i]=='?'?0:s2[i]-'a'+1;
        powb[l2-i]=numb[l2-i]*numb[l2-i];
        sm+=powb[l2-i]*numb[l2-i];
        b[l2-i].a=numb[l2-i],d[l2-i].a=powb[l2-i];
    }
}
int main(){
    scanf("%s%s",s1,s2);l1=strlen(s1)-1;l2=strlen(s2)-1;work();
    while(lim<l1+l2)lim<<=1,l++;
    for (int i=0;i<lim;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a,1),fft(b,1),fft(c,1),fft(d,1);int pos=0;
    for (int i=0;i<=lim;++i)a[i]*=d[i],b[i]*=c[i];
    fft(a,-1),fft(b,-1);
    for (int i=l2;i<=l1;++i){
        ll tmp1=(ll)(a[i].a/lim+0.5),tmp2=(ll)(b[i].a/lim+0.5);
        if (tmp2+sm-2*tmp1==0)sta[++top]=pos;pos++;
    }
    wt(top,'\n');for (int i=1;i<=top;++i)wt(sta[i],'\n');return 0;
}

点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s