[BZOJ3507/Luogu3167][CQOI2014]通配符匹配(Hash,动态规划)

发布于 2018-03-20  95 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3507/Luogu3167][CQOI2014]通配符匹配(Hash,动态规划)

Description

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

Tag

Hash,动态规划

解决思路

题意看起来很像一个“模糊”匹配的AC自动机,但是,由于直接模糊匹配需要同时在AC自动机上走若干个节点,复杂度无法保证。
分别处理每一个询问,把通配串中的所有通配符提取出来,设F[i][j]表示第i个通配符能否匹配字符串中的第j个字符。那么,若有F[i][j],F[i+1][j+len]成立的条件是通配串中从第i个通配符到第i+1个通配符之间的字符能与需要匹配的字符串的从j开始对应长度的字符串相匹配(设这个长度为len),这个可以用字符串Hash来做。
而至于*和?的分别处理,由于*可以匹配从0开始的任意长度,所以转移到[j+len],然后再一直向后转移;而?只能匹配一个,所以必须强制转移到[j+len+1]。
为了方便在最后统计处理,可以在通配串的最后加一个?,在询问串的最后加一个与字符集无关的字符#,这样就只要判断最后两个能否匹配了。
为了方便,这里使用自然溢出的Hash方法。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define ll long long
#define ull unsigned long long

const int maxN=100010;
const int Hashbase=1705;
const int inf=2147483647;

char str[maxN],SS[maxN];
ull Hash1[maxN],Hash2[maxN];
int pcnt=0,P[maxN];
ull Bret[maxN];
int F[13][maxN];

void InitHash(char *s,ull *hash);
ull GetHash(int l,int r,ull *hash);

int main()
{
    ios::sync_with_stdio(false);
    Bret[0]=1;for (int i=1;i<maxN;i++) Bret[i]=Bret[i-1]*Hashbase;
    cin>>(str+1);
    InitHash(str,Hash1);//得到通配串的Hash
    int L=strlen(str+1);
    str[++L]='?';
    //找出所有的通配符
    for (int i=1;i<=L;i++) if ((str[i]=='?')||(str[i]=='*')) P[++pcnt]=i;

    int Q;cin>>Q;
    while (Q--)//回答每一个询问
    {
        cin>>(SS+1);InitHash(SS,Hash2);
        mem(F,0);F[0][0]=1;
        int len=strlen(SS+1);SS[++len]='#';
        for (int i=0;i<pcnt;i++)
        {
            if (str[P[i]]=='*')//对于是*的,向所有后面转移,因为可以不限制长度地匹配。
                for (int j=1;j<=len;j++)
                    if (F[i][j-1]) F[i][j]=1;
            for (int j=0;j<=len;j++)//
                if (F[i][j])
                    if (GetHash(P[i]+1,P[i+1]-1,Hash1)==GetHash(j+1,j+((P[i+1]-1)-(P[i]+1))+1,Hash2))//Hash判断是否能够匹配
                    {//对于两种通配符分别转移
                        if (str[P[i+1]]=='?') F[i+1][j+((P[i+1]-1)-(P[i]+1))+1+1]=1;
                        else F[i+1][j+((P[i+1]-1)-(P[i]+1))+1]=1;
                    }
        }
        if (F[pcnt][len]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

void InitHash(char *s,ull *hash)
{
    int len=strlen(s+1);
    hash[0]=0;
    for (int i=1;i<=len;i++) hash[i]=hash[i-1]*Hashbase+s[i];
    return;
}

ull GetHash(int l,int r,ull *hash)
{
    if (r<l) return -1;
    return hash[r]-hash[l-1]*Bret[r-l+1];
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3507/Luogu3167][CQOI2014]通配符匹配(Hash,动态规划)


HNCJ OIer