BZOJ 4259 残缺的字符串

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

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

不同点在于需要再乘一个文本串，因为文本串也有通配符了... 另外貌似此题有点小卡空间？....

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 300010
#define MAXN 2000010
#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; 
}
struct cp
{
	double x,y;
	cp(double X=0,double Y=0)
	{
		x=X,y=Y;
	}
}x[MAXN],y[MAXN],ans[MAXN];
cp operator + (cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
cp operator - (cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
cp operator * (cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int m,n,lena,lenb;
char a[N],b[N];
int s[MAXN],t[MAXN],r[MAXN],L,q[N],top;
void fft(cp *a,int n,int flag)
{
	for(int i=0;i<n;i++)
	if(r[i]>i)swap(a[i],a[r[i]]);
	
	for(int i=1;i<n;i<<=1)
	{
		cp w_n(cos(M_PI/i),flag*sin(M_PI/i));
		for(int j=0;j<n;j+=i<<1)
		{
			cp w(1,0);
			for(int k=0;k<i;k++)
			{
				cp x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y,a[j+k+i]=x-y;
				w=w*w_n;
			}
		}
	}
}
int main()
{
	m=read(),n=read();
	lena=n,lenb=m;
	scanf("%s%s",a,b);
	for(int i=0;i<n;i++)
	t[i]=b[i]=='*'?0:b[i]-'a'+1;
	for(int i=0;i<m;i++)
	s[m-i-1]=a[i]=='*'?0:a[i]-'a'+1;
	
	m=n+m;
	for(n=1;n<=m;n<<=1)L++;
	for(int i=0;i<n;i++)
	r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
	
	for(int i=0;i<n;i++)
	x[i]=cp(s[i]*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(s[i]*s[i],0);
	for(int i=0;i<n;i++)
	y[i]=cp(2*t[i]*t[i],0);
	fft(x,n,1),fft(y,n,1);
	for(int i=0;i<n;i++)
	ans[i]=ans[i]-x[i]*y[i];
	
	for(int i=0;i<n;i++)
	x[i]=cp(s[i],0);
	for(int i=0;i<n;i++)
	y[i]=cp(t[i]*t[i]*t[i],0);
	fft(x,n,1),fft(y,n,1);
	for(int i=0;i<n;i++)
	ans[i]=ans[i]+x[i]*y[i];
	
	fft(ans,n,-1);
	for(int i=0;i<n;i++)
	ans[i].x/=n;
 	for(int i=0;i<=lena-lenb;i++)
    if(ans[i+lenb-1].x<0.5)
    q[++top]=i+1;
    printf("%d\n",top);
    for(int i=1;i<=top;i++)
    printf("%d ",q[i]);
}
/*
3 7
a*b
aebr*ob
*/

100

101

102

103

104

105

106

107

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 300010

#define MAXN 2000010

#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;

}

struct cp

{

double x,y;

cp(double X=0,double Y=0)

{

x=X,y=Y;

}

}x[MAXN],y[MAXN],ans[MAXN];

cp operator + (cp a,cp b){return cp(a.x+b.x,a.y+b.y);}

cp operator - (cp a,cp b){return cp(a.x-b.x,a.y-b.y);}

cp operator * (cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

int m,n,lena,lenb;

char a[N],b[N];

int s[MAXN],t[MAXN],r[MAXN],L,q[N],top;

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

{

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

if(r[i]>i)swap(a[i],a[r[i]]);

for(int i=1;i<n;i<<=1)

{

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

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

{

cp w(1,0);

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

{

cp x=a[j+k],y=w*a[j+k+i];

a[j+k]=x+y,a[j+k+i]=x-y;

w=w*w_n;

}

int main()

{

m=read(),n=read();

lena=n,lenb=m;

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

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

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

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

s[m-i-1]=a[i]=='*'?0:a[i]-'a'+1;

m=n+m;

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

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

r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));

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

x[i]=cp(s[i]*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(s[i]*s[i],0);

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

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

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

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

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

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

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

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

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

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

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

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

fft(ans,n,-1);

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

ans[i].x/=n;

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

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

q[++top]=i+1;

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

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

printf("%d ",q[i]);

}

3 7

a*b

aebr*ob

zgz233

BZOJ 4259 残缺的字符串

BZOJ 1574 [Usaco2009 Jan] 地震损坏 Damage

BZOJ [3709/4619] [[PA2014]Bohater/[Wf2016]Swap Space]

l1ll5

Comments | NOTHING

zgz233