BZOJ 4503 两个串

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4503

题意：给出模式串和文本串，模式串有通配符，问模式串在文本串的哪些位置出现了多少次。

首先 WA 死... 发现 fft 板子写错了一个符号。

终于以极大常数卡过 bzoj，结果在本校 OJ 又 CE 死...

改掉了一个由于 c++11 优化掉了导致直到现在才知道的一个错误...

另外，代码是递归版的... 迭代版会之后重写。

据说这种字符串匹配的题常用 fft...

懒得写题解了，这里的很清楚：

反转一下得到卷积的形式是常用套路...

#include <cmath>
#include <queue>
#include <cstdio>
#include <complex>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 400000
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
typedef complex<double> cp;
cp x[N],y[N],ans[N];
char a[N],b[N];
int s[N],t[N];
int p[N],top;
int n,m;
void fft(cp *a,int n,int flag)
{
    if(n==1)return ;
    cp a0[n/2+1],a1[n/2+1];
    cp w(1,0);
    cp w_n(cos(2*M_PI/n),sin(2*flag*M_PI/n));
    for(int i=0;i<n/2;i++)
    a0[i]=a[i*2],a1[i]=a[i*2+1];
    fft(a0,n/2,flag);
    fft(a1,n/2,flag);
    for(int i=0;i<n/2;i++)
    {
        a[i]=a0[i]+w*a1[i];
        a[i+n/2]=a0[i]-w*a1[i];
        w=w_n*w;
    }
}
int lena,lenb;
int main()
{
	scanf("%s%s",a,b);
	lena=strlen(a),lenb=strlen(b);
	n=lena,m=lenb;
	for(int i=0;i<n;i++)
	s[i]=a[i]-'a'+1;
	for(int i=0;i<m;i++)
	t[m-i-1]=b[i]=='?'?0:b[i]-'a'+1;
	m+=n;
	for(n=1;n<=m;n<<=1)
	
	for(int i=0;i<n;i++)
	x[i]=cp(t[i]*t[i]*t[i],0);
	for(int i=0;i<n;i++)
	y[i]=cp(1.0,0);
	fft(x,n,1),fft(y,n,1);
	for(int i=0;i<n;i++)
	ans[i]+=x[i]*y[i];
	
	for(int i=0;i<n;i++)
	x[i]=cp(s[i]*s[i],0);
	for(int i=0;i<n;i++)
	y[i]=cp(t[i],0);
	fft(x,n,1),fft(y,n,1);
	for(int i=0;i<n;i++)
	ans[i]+=x[i]*y[i];
	
	for(int i=0;i<n;i++)
	x[i]=cp(t[i]*t[i],0);
	for(int i=0;i<n;i++)
	y[i]=cp(2*s[i],0);
	fft(x,n,1),fft(y,n,1);
	for(int i=0;i<n;i++)
	ans[i]-=x[i]*y[i];
	
	fft(ans,n,-1);
	for(int i=0;i<n;i++)
	ans[i]=cp(ans[i].real()/n,ans[i].imag());
	
	for(int i=0;i<=lena-lenb;i++)
	if(ans[i+lenb-1].real()<0.5)
	p[++top]=i;
	printf("%d\n",top);
	for(int i=1;i<=top;i++)
	printf("%d\n",p[i]);
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <complex>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 400000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

typedef complex<double> cp;

cp x[N],y[N],ans[N];

char a[N],b[N];

int s[N],t[N];

int p[N],top;

int n,m;

void fft(cp *a,int n,int flag)

{

if(n==1)return ;

cp a0[n/2+1],a1[n/2+1];

cp w(1,0);

cp w_n(cos(2*M_PI/n),sin(2*flag*M_PI/n));

for(int i=0;i<n/2;i++)

a0[i]=a[i*2],a1[i]=a[i*2+1];

fft(a0,n/2,flag);

fft(a1,n/2,flag);

for(int i=0;i<n/2;i++)

{

a[i]=a0[i]+w*a1[i];

a[i+n/2]=a0[i]-w*a1[i];

w=w_n*w;

}

int lena,lenb;

int main()

{

scanf("%s%s",a,b);

lena=strlen(a),lenb=strlen(b);

n=lena,m=lenb;

for(int i=0;i<n;i++)

s[i]=a[i]-'a'+1;

for(int i=0;i<m;i++)

t[m-i-1]=b[i]=='?'?0:b[i]-'a'+1;

m+=n;

for(n=1;n<=m;n<<=1)

for(int i=0;i<n;i++)

x[i]=cp(t[i]*t[i]*t[i],0);

for(int i=0;i<n;i++)

y[i]=cp(1.0,0);

fft(x,n,1),fft(y,n,1);

for(int i=0;i<n;i++)

ans[i]+=x[i]*y[i];

for(int i=0;i<n;i++)

x[i]=cp(s[i]*s[i],0);

for(int i=0;i<n;i++)

y[i]=cp(t[i],0);

fft(x,n,1),fft(y,n,1);

for(int i=0;i<n;i++)

ans[i]+=x[i]*y[i];

for(int i=0;i<n;i++)

x[i]=cp(t[i]*t[i],0);

for(int i=0;i<n;i++)

y[i]=cp(2*s[i],0);

fft(x,n,1),fft(y,n,1);

for(int i=0;i<n;i++)

ans[i]-=x[i]*y[i];

fft(ans,n,-1);

for(int i=0;i<n;i++)

ans[i]=cp(ans[i].real()/n,ans[i].imag());

for(int i=0;i<=lena-lenb;i++)

if(ans[i+lenb-1].real()<0.5)

p[++top]=i;

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

for(int i=1;i<=top;i++)

printf("%d\n",p[i]);

}

zgz233

BZOJ 4503 两个串

BZOJ 2453 维护队列

BZOJ 3771 Triple

l1ll5

Comments | NOTHING

zgz233