6
29
2016
0

[BZOJ3507] [Cqoi2014]通配符匹配

先留下这个坑

这题我目前看到的有2种做法

做法1

做法2

占坑待填

教训:以后不能再取非常大的模数了,不然不好处理

最近因为某些原因没有更新博客……向还有在看我博客的人表示深深的歉意……

哈希,设dp[i][j]为第i个通配符的位置匹配了字符串前j位,转移基本是抄做法1的……

反正去不了绵阳了……

留下的好多的坑会一一填上。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,M=15;
const long long P=1000000003ll,base=233ll;

bool f[M][N];
int n,len,pos[M],cnt;
long long Px[N]={1},ha1[N],ha2[N];
char s[N],str[N];

long long H1(int st,int ed){
if(st>ed)return 0ll;
return ((ha1[ed]-ha1[st-1]*Px[ed-st+1])%P+P)%P;
}

long long H2(int st,int ed){
if(st>ed)return 0ll;
return ((ha2[ed]-ha2[st-1]*Px[ed-st+1])%P+P)%P;
}

int main(){
freopen("3507.in","r",stdin);
freopen("3507.out","w",stdout);
scanf("%s",str+1);
len=strlen(str+1);
str[++len]='?';
for(int i=1;i<=len;i++)if(str[i]<'a' || str[i]>'z')pos[++cnt]=i;
for(int i=1;i<=len;i++)ha1[i]=ha1[i-1]*base%P+str[i];
for(int i=1;i<=100000;i++)Px[i]=Px[i-1]*base%P;
scanf("%d",&n);
while(n--){
	scanf("%s",s+1);
	len=strlen(s+1);
	s[++len]='#';
	for(int i=1;i<=len;i++)ha2[i]=ha2[i-1]*base%P+s[i];
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=0;i<cnt;i++){
		if(str[pos[i]]=='*')for(int j=1;j<=len;j++)if(f[i][j-1])f[i][j]=1;
		for(int j=0;j<=len;j++){
            //printf("Ha1[%d,%d]=%lld , Ha2[%d,%d]=%lld\n",pos[i]+1,pos[i+1]-1,H1(pos[i]+1,pos[i+1]-1),j+1,j+pos[i+1]-pos[i]-1,H2(j+1,j+pos[i+1]-pos[i]-1));
			if(f[i][j]&&H1(pos[i]+1,pos[i+1]-1)==H2(j+1,j+pos[i+1]-pos[i]-1)){
				if(str[pos[i+1]]=='?')f[i+1][j+pos[i+1]-pos[i]]=1;
                else f[i+1][j+pos[i+1]-pos[i]-1]=1;
			}
		}
    }
    puts(f[cnt][len]?"YES":"NO");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 643

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com