CQOI 2014 通配符匹配（动态规划+哈希）

发表于 |
字数统计: 923字 | 阅读时长 ≈ 4min

【CQOI2014】通配符匹配

问题描述

几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号“*”，可以匹配0个即以上任意的字符；另一个是问号“?”，可以匹配恰好一个任意字符。

现在需要你编写一个程序，对于给定文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。

第二行包含一个整数n，表示文件的个数。

接下来n行，每行为一个仅含小写字母的字符串，表示文件名列表。

输出格式

输出n行，每行为“YES”或“NO”，表示对应文件能否被通配符匹配。

样例输入

*abc?e**e

3

abcee

ppabcqexe

abcdefgee

样例输出

NO

YES

YES

提示

对于30%的数据，字符串长度不超过100

对于100%的数据，字符串长度不超过100000，1<=n<=100，通配符个数不超过10个。

通配符的个数比较少，考虑按照通配符来dp

令$F[i][j]$表示用完前$i$个通配符，能否匹配前$j$个字符。令$s$为含通配符串，$t$为文件串，$pos[i]$表示第$i$个通配符的位置。

那么根据通配符的类型来考虑$F[i][j]$的转移

如果第$i+1$个通配符是$”?”$

那么需要判断$s[pos[i]+1],pos[i+1]-1]$和$t[j+1,j+pos[i+1]-pos[i]-1]$是否相同，如果相同，并且$F[i][j]$为真，那么$F[i+1][j+pos[i+1]-pos[i]]$为真。注意$”?”$必须匹配。

如果第$i+1$个通配符是$”*”$

那么同样需要判断$s[pos[i]+1],pos[i+1]-1]$和$t[j+1,j+pos[i+1]-pos[i]-1]$是否相同，如果相同，且$F[i][j]$为真，那么$j+pos[i+1]-pos[i]-1$及之后的位置都为真了。此时只需要先将$F[i+1][j+pos[i+1]-pos[i]-1$置为真，然后最后跑一个$F[i+1][j]|=F[i+1][j-1]$即可。

注意到为了不讨论最后一个通配符后面的部分，可以在$s$后面加一个$”?”$，在$t$后面随便加一个字符即可。

复杂度$O(nklen)，k为通配符个数$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll unsigned long long
#define N 200005
using namespace std;
const ll p=131;
char A[N],B[N];
bool F[12][N];
int n,pos[12],L1,L2,cnt;
ll Aash[N],Bash[N],Pow[N];
ll Get(ll Hash[],int l,int r)
{return l>r?0:Hash[r]-Hash[l-1]*Pow[r-l+1];}
int main()
{
	int k,x,y;ll t1,t2;
	scanf("%s%d",A+1,&n);
	L1=strlen(A+1);A[++L1]='?';Pow[0]=1;
	for(register int i=1;i<N;i++)Pow[i]=Pow[i-1]*p;
	for(register int i=1;i<=L1;i++)Aash[i]=Aash[i-1]*p+A[i];
	for(register int i=1;i<=L1;i++)if(A[i]=='*'||A[i]=='?')pos[++cnt]=i;
	while(n--)
	{
		scanf("%s",B+1);L2=strlen(B+1);B[++L2]='?';
		for(register int i=1;i<=L2;i++)Bash[i]=Bash[i-1]*p+B[i];
		for(register int i=0;i<=cnt;i++)
		for(register int j=0;j<=L2;j++)F[i][j]=0;
		F[0][0]=1;
		for(register int i=0;i<cnt;i++)
		{
			for(register int j=0;j<L2;j++)if(F[i][j])F[i+1][j+pos[i+1]-pos[i]-(A[pos[i+1]]!='?')]=Get(Aash,pos[i]+1,pos[i+1]-1)==Get(Bash,j+1,j+pos[i+1]-pos[i]-1);
			if(A[pos[i+1]]=='*')for(register int j=1;j<=L2;j++)F[i+1][j]|=F[i+1][j-1];
		}
		F[cnt][L2]?puts("YES"):puts("NO");
	}
}