CQOI2014 通配符匹配

发表于
字数统计: 1,045字 | 阅读时长 ≈ 5min

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。设$bool$类型的$f[i][j]$表示用完前$i$个通配符，是否能完成1~$ j$位置的匹配。

分别考虑两种类型的通配符的转移。相同点是，两个通配符之间的字符串是必须完全相同的，这个可以用Hash来判断。

下面考虑$f[i][j]$的状态转移。设第$i$个通配符的位置是$pos[i]$，含有通配符的字符串是$s$，文件字符串是$t$。

  1. 第$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]]$为真，否则为假。注意这里是“$j+pos[i+1]-pos[i]$”而不是“$j+pos[i+1]-pos[i]-1$”，因为’?’本身也需要匹配。
  2. 第$i+1$个通配符是’*’。此时只要$s[pos[i]+1,pos[i+1]-1]$与$t[j+1,j+pos[i+1]-pos[i]-1]$相同，那么$t$之后的位置就都可以匹配了。所以对于这一部分，在匹配成功且$f[i][j]$为真的情况下，只需要把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
38
39
40
41
42
43
44
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 100005
#define ull unsigned long long
using namespace std;

bool f[12][MAXN];
int pos[12],k,len;
ull pw[MAXN],inv[MAXN],Hash[MAXN][2];
char s[MAXN],t[MAXN];

void prehash(char a[],int len,int ty){
	for(int i=1;i<=len;i++)Hash[i][ty]=Hash[i-1][ty]*131+a[i];
}

ull gethash(int l,int r,int ty){
	if(r<l)return 0;
	return Hash[r][ty]-Hash[l-1][ty]*pw[r-l+1];
}


int main(){
	int i,j,cs;
	for(i=1,pw[0]=1;i<=100000;i++)pw[i]=pw[i-1]*131;
	scanf("%s",s+1);len=strlen(s+1);s[++len]='?';
	prehash(s,len,0);
	for(i=1;i<=len;i++)if(s[i]=='*'||s[i]=='?')pos[++k]=i;
	scanf("%d",&cs);
	while(cs--){
		scanf("%s",t+1);len=strlen(t+1);t[++len]='%';
		prehash(t,len,1);
		memset(f,false,sizeof(f));
		f[0][0]=true;
		for(i=0;i<k;i++){
			for(j=0;j<=len;j++)if(f[i][j]){
				if(s[pos[i+1]]=='*')f[i+1][j+pos[i+1]-pos[i]-1]=gethash(j+1,j+pos[i+1]-pos[i]-1,1)==gethash(pos[i]+1,pos[i+1]-1,0);
				else f[i+1][j+pos[i+1]-pos[i]]=gethash(j+1,j+pos[i+1]-pos[i]-1,1)==gethash(pos[i]+1,pos[i+1]-1,0);
			}
			if(s[pos[i+1]]=='*')for(j=1;j<=len;j++)f[i+1][j]|=f[i+1][j-1];
		}
		puts(f[k][len]?"YES":"NO");
	}
}