「codechefTASTRMAT」String Matching

2014年12月28日2,9140

其实我没有参赛。。。在比赛时间被人拉去做了这一道。。。

~~你们就坑我吧~~

设L=n-m

对于B的第1个字符，其匹配的是A的一个区间1到1+L

若其与A[1]不同，则hash值增加100001^m

与A[1+K]不同，则hash值增加100001^(n-K)

用数据结构支持查询1到1+L对hash值的贡献

即第K位与B的第1个字符不同则hash值增加100001^(n-K)，相同增加0

用个线段树or树状数组（实际上前缀和就行）

接着考虑

对于B的第2个字符，其匹配的是A的一个区间2到2+L

若其与A[2]不同，则hash值增加100001^n

与A[2+K]不同，则hash值增加100001^(n-K)

……

我们发现，线段树每个位置的hash值每次应除以100001

于是，我们预处理100001^K在mod 1000000007意义下的逆元

唉我用个暴力找出100001^K的逆元是943660570^K（真是逗。。。）

对于B的第i个字符，将hash值乘上100001^(m-i+1)的逆元，最后累加hash值即可

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define P 943660570
#define ll long long
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll ans;
int n,m,T;
char ch[100005]; 
int a[100005],b[100005];
ll H[100005],ine[100005];
struct seg{
	int l,r;ll c[2];
}t[400005];
void update(int k)
{
	t[k].c[0]=(t[k<<1].c[0]+t[k<<1|1].c[0])%mod;
	t[k].c[1]=(t[k<<1].c[1]+t[k<<1|1].c[1])%mod;
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r)
	{
		t[k].c[a[l]]=H[n-l+1];
		t[k].c[a[l]^1]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	update(k);
}
int query(int k,int x,int y,int f)
{
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(x==l&&y==r)
		return t[k].c[f];
	if(y<=mid)return query(k<<1,x,y,f);
	else if(x>mid)return query(k<<1|1,x,y,f);
	else return (query(k<<1,x,mid,f)+query(k<<1|1,mid+1,y,f))%mod;
}
int main()
{
	H[1]=1;for(int i=2;i<=100000;i++)H[i]=H[i-1]*100001%mod;
	ine[1]=1;for(int i=2;i<=100000;i++)ine[i]=ine[i-1]*P%mod;
	scanf("%s",ch+1);n=strlen(ch+1);
	for(int i=1;i<=n;i++)
		a[i]=ch[i]-'0';
	build(1,1,n);
	T=read();
	while(T--)
	{
		ans=0;
		scanf("%s",ch+1);m=strlen(ch+1);
		for(int i=1;i<=m;i++)b[i]=ch[i]-'0';
		int L=n-m;
		for(int i=1;i<=m;i++)
		{
			ll t=query(1,i,i+L,b[i]^1);
			t=t*ine[m-i+1]%mod;
		   	ans=(ans+t)%mod;
		}
		cout<<ans<<endl;
	}
	return 0;
}

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define P 943660570

#define ll long long

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

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

return x;

}

ll ans;

int n,m,T;

char ch[100005];

int a[100005],b[100005];

ll H[100005],ine[100005];

struct seg{

int l,r;ll c[2];

}t[400005];

void update(int k)

{

t[k].c[0]=(t[k<<1].c[0]+t[k<<1|1].c[0])%mod;

t[k].c[1]=(t[k<<1].c[1]+t[k<<1|1].c[1])%mod;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;

if(l==r)

{

t[k].c[a[l]]=H[n-l+1];

t[k].c[a[l]^1]=0;

return;

}

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

update(k);

}

int query(int k,int x,int y,int f)

{

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(x==l&&y==r)

return t[k].c[f];

if(y<=mid)return query(k<<1,x,y,f);

else if(x>mid)return query(k<<1|1,x,y,f);

else return (query(k<<1,x,mid,f)+query(k<<1|1,mid+1,y,f))%mod;

}

int main()

{

H[1]=1;for(int i=2;i<=100000;i++)H[i]=H[i-1]*100001%mod;

ine[1]=1;for(int i=2;i<=100000;i++)ine[i]=ine[i-1]*P%mod;

scanf("%s",ch+1);n=strlen(ch+1);

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

a[i]=ch[i]-'0';

build(1,1,n);

T=read();

while(T--)

{

ans=0;

scanf("%s",ch+1);m=strlen(ch+1);

for(int i=1;i<=m;i++)b[i]=ch[i]-'0';

int L=n-m;

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

{

ll t=query(1,i,i+L,b[i]^1);

t=t*ine[m-i+1]%mod;

ans=(ans+t)%mod;

}

cout<<ans<<endl;

}

return 0;

}

« 「CF498D」Traffic Jams in the Land 「BZOJ2186」[SDOI2008] 沙拉公主的困惑 »

hzwer.com _ Home | http://hzwer.com

「codechefTASTRMAT」String Matching

分类目录

热门文章

Myfriends

近期评论