P3167 通配符匹配
letitdown
·
·
题解
Upd in 12.21:
由于没有判一个串能匹配的最小长度所以被 hack 了。。。
修改了 latex，改了一下马蜂，补了一下锅。(之前的马蜂过于丑了)
具体就体现在下面新添加的 cntc 变量。
题意
本题的意思就是给出一段带有 ? 与 * 的字符串(在下面称为 s)，? 必须占据一个字符位置，* 可以占据任意位置，
求下面给出几段(在下面称为 ss)中能够匹配的字符串。
思路
前言
本题最可恶的一点是，如果 s 的第一段/最后一段是字符，那么 ss 中最开始/最后也必须是一样的字符。
另外，本题我使用了 hash + 前缀，如果不太熟悉的话可以了解一下～传送门
举个栗子～
如样例，s 为 *aca?ctc，我们就可以将它分为
对于每一段，我们用一个 $add$ 数组来判断它的种类，
用 $co$ 记录它的段数，字符串对应 2,$*$ 对应 1,$?$ 对应 0：
```cpp
scanf("%s",s+1);lens=strlen(s+1);
if(s[1]<'a'||s[1]>'z')co=0;else add[1]=2;
for(register int i=1;i<=lens;i++){
if((s[i]>='a'&&s[i]<='z')||(s[i]=='?'))cntc++;
if(s[i]>='a'&&s[i]<='z'){
len[co]++;
f[co]=f[co]*131+s[i];
}
else if(s[i]=='*') {add[++co]=1;if(i!=lens&&s[i+1]>='a'&&s[i+1]<='z')add[++co]=2;}
else{co++;if(i!=lens&&s[i+1]>='a'&&s[i+1]<='z')add[++co]=2;}
}
```
注意，由于开头字符不好判断，所以这里加了一个特判，
来记录开头是字符串的情况。
#### 判断
预处理好了，那么，如何进行判断呢？
首先，我们需要算出原串最少要匹配多少字符，如果询问串长度比这个还要小就直接判否。
这里，我用了 $doit$ 与 $ask$ 两个自定义函数，
doit 用来对可以自由匹配的字符种类进行判断处理，
ask 用来对“ ？ ”后的字符进行判断处理。
两个函数中都使用了 key，k 两个参数，
key 记录了到哪个字符（指针），k 记录了到第几段。
对于 doit：
```cpp
inline void doit(int key,int k){
if(k>co){can=1;return;}
if(add[k]==2){
for(register int i=key+len[k]-1;i<=le;i++)
if(ff[i]-ff[i-len[k]]*p[len[k]]==f[k])
{doit(i+1,k+1);if(can)return;}
return;
}
if(add[k]==1){
doit(key,k+1);
if(can)return;
return;
}
if(add[k]==0){
ask(key+1,k+1);return;
}
}
```
对于 ask：
```cpp
inline void ask(int key,int k){
if(k>co){can=1;return;}
if(add[k]==2){
if(ff[key+len[k]-1]-ff[key-1]*p[len[k]]==f[k])doit(key+len[k],k+1);
}
else{
if(add[k]==1){if(add[k+1]==0){for(register int i=key+2;i<=le;i++)if(ff[i+len[k+2]-1]-ff[i-1]*p[len[k+2]]==f[k+2])doit(i+len[k+2],k+3);}doit(key,k+1);}
else ask(key+1,k+1);
}
}
```
#### 收尾
到这里，万事俱备，只欠东风，进行我们华丽的结束吧～
接下来就该读入与判断了：
```cpp
p[0]=1;
for(register int i=1;i<=100000;i++)p[i]=p[i-1]*131;
int n=read();
while(n--){
can=0;
scanf("%s",ss+1);le=strlen(ss+1);
if(cntc>le){puts("NO");continue;}
for(register int i=1;i<=le;i++)ff[i]=ff[i-1]*131+ss[i];
if(add[1]==2)if(ff[len[1]]-ff[0]*p[len[1]]!=f[1]){printf("NO\n");continue;}
if(add[co]==2)if(ff[le]-ff[le-len[co]]*p[len[co]]!=f[co]){printf("NO\n");continue;}
doit(1,1);
if(can)printf("YES\n");else printf("NO\n");
}
```
## CODE
------------
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
namespace EMT{
#define ull unsigned long long
inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x;}
char s[100005],ss[100005];
int lens,len[25],co=1,le,k,key,cnt,add[25];bool can;
ull f[25],ff[100010],p[100010];
int cntc;
inline void ask(int,int);
inline void doit(int,int);
inline void ask(int key,int k){
if(k>co){can=1;return;}
if(add[k]==2){
if(ff[key+len[k]-1]-ff[key-1]*p[len[k]]==f[k])doit(key+len[k],k+1);
}
else{
if(add[k]==1){if(add[k+1]==0){for(register int i=key+2;i<=le;i++)if(ff[i+len[k+2]-1]-ff[i-1]*p[len[k+2]]==f[k+2])doit(i+len[k+2],k+3);}doit(key,k+1);}
else ask(key+1,k+1);
}
}
inline void doit(int key,int k){
if(k>co){can=1;return;}
if(add[k]==2){
for(register int i=key+len[k]-1;i<=le;i++)
if(ff[i]-ff[i-len[k]]*p[len[k]]==f[k])
{doit(i+1,k+1);if(can)return;}
return;
}
if(add[k]==1){
doit(key,k+1);
if(can)return;
return;
}
if(add[k]==0){
ask(key+1,k+1);return;
}
}
inline short main(){
scanf("%s",s+1);lens=strlen(s+1);
if(s[1]<'a'||s[1]>'z')co=0;else add[1]=2;
for(register int i=1;i<=lens;i++){
if((s[i]>='a'&&s[i]<='z')||(s[i]=='?'))cntc++;
if(s[i]>='a'&&s[i]<='z'){
len[co]++;
f[co]=f[co]*131+s[i];
}
else if(s[i]=='*') {add[++co]=1;if(i!=lens&&s[i+1]>='a'&&s[i+1]<='z')add[++co]=2;}
else{co++;if(i!=lens&&s[i+1]>='a'&&s[i+1]<='z')add[++co]=2;}
}
p[0]=1;
for(register int i=1;i<=100000;i++)p[i]=p[i-1]*131;
int n=read();
while(n--){
can=0;
scanf("%s",ss+1);le=strlen(ss+1);
if(cntc>le){puts("NO");continue;}
for(register int i=1;i<=le;i++)ff[i]=ff[i-1]*131+ss[i];
if(add[1]==2)if(ff[len[1]]-ff[0]*p[len[1]]!=f[1]){printf("NO\n");continue;}
if(add[co]==2)if(ff[le]-ff[le-len[co]]*p[len[co]]!=f[co]){printf("NO\n");continue;}
doit(1,1);
if(can)printf("YES\n");else printf("NO\n");
}
return 0;
}
}
int main(){return EMT::main();}
```
#### 结语
这道题我也调了有好久了，甚至都有些舍不得了，所以写下了本篇题解，也是我的第一篇题解
如果对你有帮助，求个赞qwq