[CQOI2014] 通配符匹配

题目描述

几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号（*），可以匹配 0 个及以上的任意字符：另一个是问号（?），可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数 \(n\)，表示文件个数。接下来 \(n\) 行，每行为一个仅包含小写字母字符串，表示文件名列表。

输出格式

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

样例 #1

样例输入 #1

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

样例输出 #1

YES
YES
YES
YES
YES
NO

提示

对于 \(100 \%\) 的数据

• 字符串长度不超过 \(100000\)
• \(1 \le n \le 100\)
• 通配符个数不超过 \(10\)

解析

这个题大意是让我们用一个模式字符串(带一些特殊符号的),让我们去对应匹配它给出的各个字符串.
? 可以替换一个字符,* 可以替换一堆字符,让你看看这些输入的串中有哪些可以匹配,哪些不可以.
然后就想想思路,貌似挺简单.
1.写这个题的时候还没开KMP,现在看起来KMP是可以解决的,把模式串根据通配符拆开,看各个串是否能够匹配是可行的.
2.如果写最基础的dfs貌似也很简单,就是对于* 一个一个字符试过去,对于? 跳过当前匹配,而且很好的是它不会超时,但当时有人卡掉了DFS.
3.那就可以用dp了,将阶段与状态构思一下,让每个分串作为阶段(只有上一个串匹配,才可匹配下一个串),让字符串的总长作为状态,跟上面一样让通配符作为分解将串分开,一个分串(长度为sublen)的hash值如果能够对应上我们输入串的某个部分[j,i],(i-j+1=sublen),当出现匹配的时候就进行串上某位置到另一位置的转移(i-sublen->i),到最后如果串尾状态为1,则为yes,否则为no.
然而dfs怎么能够遇到一点小小的困难就放弃呢.
既然问题在于超时,那就想想剪枝吧,我们之前的dfs是一个个字符匹配过去,现在我们换成用分串的hash值匹配.
也就是说我们这么做,dfs的层数最多是11层(因为通配符最多10个).
那再想想这个dfs在通配符处如何处理.
我们用一个数组(此处用的是br)保存通配符种类,* 为0,? 为1(主要因为我用的三目^$* $),再以此分开处理就好.
怎么处理呢,如果遇到的是? ,就让它在待匹配串上跳过一位,让该? 后缀的分串去和待匹配串剩下的部分匹配.
如果遇到的是* ,就让它后缀的分串往后不断去匹配各个串,直到我们无可匹配.
还是不放心复杂度,万一就超时了呢,所以我们再加一个剪枝.
假设我们这个串有两个* 而第一个* 的后缀串已经对应上了待匹配串的一部分,但是第二个* 和剩下的位置均无法匹配,那么我们如果以我们朴素搜索策略,会再次返回到第一个* 的位置继续尝试.
但是仔细分析会发现,如果我们已经到达了最后一个* 的位置,它在第一次被尝试时不行,之后也一定不行,因为我们尝试的位置是我们第一次已经尝试过的位置.
所以说在第一次达到最深的* 尝试完所有的可能匹配位置后这个串没有被匹配,那么就用flag标记上,直接return false.
这样就100%不超时了.
其实还有一个优化,用待匹配串的剩余长度与剩余分串的总长进行比较(在代码中用est与st数组存储分串与串长,nowlen表示待匹配串长度),如果剩余长度比当前总长小,就return 0;
然而拥有废物码风的我带上这个剪枝就炸了
如果细心观察的话,其实我们的dfs在这样的匹配方式下就是进行了优化的dp,而且省去了一些无用的比较,是会更快些的.
至此结束了?然而还是他有个人将自然溢出卡没了.
所以就补上了带模数hash(貌似是自己第一次写带模数hash,要把格式记住.)
码风很差,你忍一下.

正解代码

#include<bits/stdc++.h>
#define qr qr()
#define llu unsigned long long
#define ll long long
using namespace std;

const int N=1e5+50000,base=131,mod=1001992007;
int n,len,nowlen,top,est[11],st[11];
//双模数hash. 
llu ha1[N],ha2[N],opha1[12],opha2[12],p1[N],p2[N],ebr[N];
char s[N],cop[11],a[N];
bool br[11],fl,flag;
llu gethash1(int l,int r)
{
	return ha1[r]-ha1[l-1]*p1[r-l+1];
}
ll gethash2(int l,int r)
{
	return (ha2[r]-ha2[l-1]*p2[r-l+1]%mod+mod)%mod;
}
bool dfs(int now,int l)
{
//	printf("%d(%d&&%d)",now,l,br[now]);
	//边界条件有多种可能:
	//1.最后所有分串都被匹配,待匹配串刚好用完 return 1. 
	//2.最后所有分串都被匹配,但是待匹配串没被用完 return 0.
	//3.最后剩下的是一个*,可以匹配剩下的所有字符 return 1. 
	if(now>top&&l>nowlen)return 1;
	else if(now>top&&l<=nowlen)return 0;
	else if(!br[now]&&now==top)return 1;
	if(br[now])
	{
		if(st[now]==0) return dfs(now+1,l+br[now+1]);//特判串长为0(两个通配符挨着) 
//		printf("%d,%llu %llu\n",st[now],gethash1(l,l+st[now]-1),opha1[now]);
		if(gethash1(l,l+st[now]-1)==opha1[now]&&gethash2(l,l+st[now]-1)==opha2[now]) 
			return dfs(now+1,l+st[now]+br[now+1]);
		else return 0;
	}
	else
	{
		if(!st[now])
		{//我的写法没有将每个通配符单作一个串处理. 
		//所以每个地方都要特判一个串是否为空串不然hash会越界而且无法处理... 
		// 最复杂的一集. 
			while(!flag&&nowlen>=l-1+est[now]+ebr[now])
			{
//				printf("%d:(%d|%d)",now,l,st[now]);
				if(dfs(now+1,l+br[now+1]))return 1;
				++l;
			}
		} else
		{
			int r=l+st[now]-1;
			while(!flag&&nowlen>=r)
			{
//				printf("%d:(%d,%d|%d)",now,l,r,st[now]);
//				printf("%llu,%llu\n",gethash1(l,r),opha1[now]);
				if(gethash1(l,r)==opha1[now]&&gethash2(l,r)==opha2[now])//,gethash2(l,r),opha2[now]
					if(dfs(now+1,r+1+br[now+1]))return 1;
				++l,++r;
			}
		}
		flag=1;
		return 0;
	}
}
void init()
{
	//prework 
	char op;
	p1[0]=1,p2[0]=1,br[0]=1;
	for(int i=1;i<=(1e5);++i)
	{
		p1[i]=p1[i-1]*base;
		p2[i]=p2[i-1]*base%mod;
	}
	while(1)
	{
		op=getchar();
		if(op==' '||op=='\n')
		{
			st[top]=len-est[top-1];
			break;
		}
		if(!(op^'*')||!(op^'?'))
			st[top]=len-((top>=1)?est[top-1]:0),len+=((op^'*')?1:0),est[top]=len,br[++top]=(op^'*');
		else opha1[top]=opha1[top]*base+op,opha2[top]=(opha2[top]*base%mod+op)%mod,++len;
	}
	for(int i=top;i;--i)ebr[i]=ebr[i+1]+br[i];
//	for(int i=0;i<=top;++i)printf("%d ",st[i]);
//	putchar('\n');
//	for(int i=0;i<=top;++i)printf("%d ",br[i]);
//	putchar('\n');
//	for(int i=0;i<=top;++i)printf("%llu ",opha1[i]);
	scanf("%d",&n);
	//剪枝dfs? 
	for(int i=1;i<=n;++i)
	{
		flag=0;
		scanf("%s",s+1);
		nowlen=strlen(s+1);
		if(nowlen<len)
		{ 
			printf("NO\n");
			continue;
		}
		for(int now=1;now<=nowlen;++now)
			ha1[now]=ha1[now-1]*base+s[now],ha2[now]=((ha2[now-1]*base)%mod+s[now])%mod;
		//超时怎么办. 
		//可行性剪枝呗,出现一个*后,后面的串无法匹配,就break.近似极限复杂度为O(n*N)绰绰有余. 
		if(dfs(0,1))printf("YES\n");
		else printf("NO\n");
	}
}
int main()
{
	init();
	return 0;
}
/*
*aca?ctc*
10
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct
aggggcaacctct
aggggcaacatctcvvv
acaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacacaactc
cacatctcc
rbwhqbyehwrqlrzw?*?wy*?*pybzyllklojxjequqqpkr??yxnqwxrdszz*aca?ctc
2
rbwhqbyehwrqlrzwzwwytpybzyllklojxjequqqpkrhhyxnqwxrdszzacaacatctc
rbwhqbyehwrqlrzwzwwytasfvertvetpybzyllklojxjequqqpkrhhyxnqwxrdszzacaactc
*/