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

· · 题解

震惊！没看明白楼下玄学思路

什么各种KMP，DP，HASH，各种玄学疯狂操作，码长震惊，本蒟蒻表示并没有看懂怎么办（呆呆的吃手指~）

那怎么办啊，我又不想呆呆的看着他WA0，可怕

玄学思路突现脑中，爆搜？差不多

#include<bits/stdc++.h>
using namespace std;
char ch[100001],wzc[100001];
int n;
bool _doudou(int x,int y)//开始爆搜，从后往前搜，避免有的点故意卡你，其实也是为了方便 
{
    if(y==0)//如果匹配串到头了 
    {
        if(x==0)return 1;//通配符串也被吃完了，肯定没问题 
        for(int i=x;i>0;i--)//开始爆搜剩下的'*' 
            if(ch[i]!='*')return 0;//如果还有，肯定不行 
        return 1;//没了，就没问题 
    }
    if(!x)return 0;//如果通配符串先挂完了，就肯定挂了 
    if(ch[x]=='*')//如果搜到了一个'*' 
    {
        for(int i=y;i>=0;i--)//就从剩下的所有的位置开始搜，时间复杂度看起来很高，但是试想几乎所有的情况在搜了一下之后就会跳出，其实也并不复杂 
            if(_doudou(x-1,i))return 1;
    }
    else
    {
        if(wzc[y]==ch[x]||ch[x]=='?')return _doudou(x-1,y-1);//如果是一个'?'，就让两个串都向前走一位 
        else return 0;//挂喽 
    }
}
int main()
{
    scanf("%s%d",ch+1,&n);//读入,QwQ~ 就是想卖个萌 
    int len=strlen(ch+1);
    while(n--)
    {
        scanf("%s",wzc+1);
        if(_doudou(len,strlen(wzc+1)))printf("YES\n");//没为题就输出YES 
        else printf("NO\n");//否则NO 
    }
    return 0;//祝你幸福~ 
}

我感觉码长还可以，而且跑的飞快（自我感觉良好）

而且比较适合初学者叭?