CQOI2014 通配符匹配

P3167 [CQOI2014] 通配符匹配

题目大意

常见的通配符有以下两种：

• *：可以匹配$0$个及以上的任意字符
• ?：可以匹配一个任意字符

给定一个由通配符和小写字母组成的字符串$S$和$n$个由小写字母组成的字符串$T_i$，求每个$T_i$能否被通配字符串$S$通配。

$1\le n\le 100$

字符串长度不超过$10^5$，通配符个数不超过$10$

题解

依题意，通配符个数不超过$10$，那么我们可以以通配符为界限，将通配串分为若干段。

设通配串能分为$m$段（也就是有$m?1$个通配符），$o{p}_i$表示第$i$段之前的通配符（$0$表示没有，$1$表示?，$2$表示*），$le{n}_i$表示第$i$段的长度。

对于每个$T_k$，我们考虑如何判断其能否被通配字符串通配。设$f_{i,j}$表示第$i$段的结尾能否匹配上$T_k$的第$j$个字符。那么，转移方程为

$$f_{i,j}=?\begin{array}{cc}{f}_{i?1,j?le{n}_i}& o{p}_i=0\\ f_{i?1,j?le{n}_i?1}& o{p}_i=1\\ \sum _{t=0}^{j?le{n}_i}{f}_{i?1,k}& o{p}_i=2\end{array}$$

用哈希来判断能否转移即可。

答案为$f_{m,|T_k|}$。

时间复杂度为$O(|S|+m\sum |T_k|)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
const int base=31;
const long long mod=1e9+7;
int T,s1,t1,w1=0,f[15][N+5];
long long bw[N+5],h[N+5],sf[15][N+5];
char s[N+5],t[N+5];
struct node{
	int bg,ed,op;
	long long hsh;
}w[15];
void init(){
	bw[0]=1;
	for(int i=1;i<=N;i++){
		bw[i]=bw[i-1]*base%mod;
	}
}
void solve_s(){
	s1=strlen(s+1);
	w[++w1].bg=1;
	w[w1].op=0;
	for(int i=1;i<=s1;i++){
		if(s[i]=='?'||s[i]=='*'){
			w[w1].ed=i-1;
			w[++w1].bg=i+1;
			if(s[i]=='?') w[w1].op=1;
			else w[w1].op=2;
		}
	}
	w[w1].ed=s1;
	for(int i=1;i<=w1;i++){
		w[i].hsh=0;
		for(int j=w[i].bg;j<=w[i].ed;j++){
			w[i].hsh=(w[i].hsh*base+s[j]-'a'+1)%mod;
		}
	}
}
void solve_t(){
	t1=strlen(t+1);
	for(int i=1;i<=t1;i++){
		h[i]=(h[i-1]*base+t[i]-'a'+1)%mod;
	}
}
long long gthsh(int l,int r){
	return (h[r]-h[l-1]*bw[r-l+1]%mod+mod)%mod;
}
void solve_dp(){
	for(int i=0;i<=w1;i++){
		for(int j=0;j<=t1;j++) sf[i][j]=f[i][j]=0;
	}
	if(gthsh(1,w[1].ed-w[1].bg+1)!=w[1].hsh) return;
	f[1][w[1].ed-w[1].bg+1]=1;
	for(int i=2;i<=w1;i++){
		sf[i-1][0]=f[i-1][0];
		for(int j=1;j<=t1;j++){
			sf[i-1][j]=sf[i-1][j-1]|f[i-1][j];
		}
		int len=w[i].ed-w[i].bg+1;
		for(int j=1;j<=t1;j++){
			if(w[i].op==1){
				if(j-len-1>=0&&gthsh(j-len+1,j)==w[i].hsh){
					f[i][j]=f[i-1][j-len-1];
				}
			}
			else{
				if(j-len>=0&&gthsh(j-len+1,j)==w[i].hsh){
					f[i][j]=sf[i-1][j-len];
				}
			}
		}
	}
}
int main()
{
	init();
	scanf("%s",s+1);
	solve_s();
	scanf("%d",&T);
	while(T--){
		scanf("%s",t+1);
		solve_t();
		solve_dp();
		if(f[w1][t1]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}