通配符匹配

这一道题听说可以用AC自动机来做

但是我觉得我们可以让AC自动机去AC别的题目，用最简单的

字符串哈希

就可以了

当然还是要跑$dp$的qwq

我们可以设定$bool$型的$f[i][j]$表示

前面原字符串的前$i$个字符与待匹配的字符串的前$j$个字符匹配

如果当前通配符是'*'的话，只要当前匹配了，那么后面所有的都可以匹配

如果在两个通配符之间的字符全部匹配（用$hash$处理）

都可以打标记

但如果当前通配符是'?'的话，不能给当前字符打标记，要跳到下一个

因为'?'只能匹配一个字符

初始化的话

就是$f[0][0]=1$

因为一个字符都没有的两个空串是匹配的

关于代码

我的码风十分奇怪，能看得懂就行

其中$tpf$，顾名思义，就是通配符

两个$h$分别表示原字符串和待处理字符串的哈希前缀和

另外，我是用字符串存的，为了方便处理，我在每个字符串前都加上个空格

还有一个比较重要的

如果原字符串最后一个字符不是通配符的话

后面的字符是匹配不到的

所以我在原字符串后面加了一个'?'，为了不改变字符串值，所以在每一个待处理字符串前都要加上任意一个字符

code

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=100010;
int n,m,k,tpf[50],cnt,ans;
ull h1[N],h2[N],t[N],b=1331;
string s,str;
bool f[20][N];
int main(){
	cin>>s;
	s=' '+s+'?';
	n=s.size()-1;
	t[0]=1;
	for(int i=1;i<N;i++)t[i]=t[i-1]*b;
	for(int i=1;i<=n;i++){
		h1[i]=h1[i-1]*b+s[i];
		if(s[i]=='*'||s[i]=='?')tpf[++cnt]=i;
	}
	scanf("%d",&k);
	while(k--){
		cin>>str;
		str=' '+str+'a';
		m=str.size()-1;
		for(int i=1;i<=m;i++)h2[i]=h2[i-1]*b+str[i];
		memset(f,0,sizeof(f));
		f[0][0]=1;
		for(int i=0;i<=cnt;i++){
			if(s[tpf[i]]=='*')for(int j=1;j<=m;j++)if(f[i][j-1])f[i][j]=1;
			for(int j=0;j<=m;j++){
				if(!f[i][j])continue;
				register int lt=tpf[i]+1,rt=tpf[i+1]-1,ls=j+1,rs=j+(rt-lt+1);
				if(h1[rt]-h1[lt-1]*t[rt-lt+1]==h2[rs]-h2[ls-1]*t[rs-ls+1])
					f[i+1][rs+(s[tpf[i+1]]=='?')]=1;
			}
		}
		puts(f[cnt][m]?"YES":"NO");
	}
}

另外，这一道题和病毒检测也很相似，大家也可以去$A$一下