题解 P3167 【[CQOI2014]通配符匹配】

· · 题解

通配符匹配

这一道题听说可以用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一下