【bzoj3507】[Cqoi2014]通配符匹配

2015.06.24 19:44 Wed | 22次阅读 | 旧日oi | 固定链接 | 源码

Description

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

HINT

对于1 00%的数据
·字符串长度不超过1 00000
·  1 <=n<=100
·通配符个数不超过10

题解

dp[i][j]表示前i个匹配符能否匹配当前串的前j个字符,然后中间的部分用hash判断一下就行了。注意有一些小细节,比如“*”和“?"的区别。看代码吧。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define ull unsigned long long
#define BASE 13131
char str[N],s[N];
int pos[15];
bool dp[15][N];
int n,len,cnt;
ull n1[N],n2[N],power[N];
ull h1(int st,int ed)
{
    if(st>ed) return 0;
    return n1[ed]-n1[st-1]*power[ed-st+1];
}
ull h2(int st,int ed)
{
    if(st>ed) return 0;
    return n2[ed]-n2[st-1]*power[ed-st+1];
}
int main()
{
    int i,j;
    scanf("%s",str+1);
    len=strlen(str+1);
    for(i=1;i<=len;i++)
        if(!isalpha(str[i])) pos[++cnt]=i;
    pos[++cnt]=len+1;str[++len]='?';
    for(i=1;i<=len;i++)
        n1[i]=(n1[i-1]*BASE+str[i]);
    for(power[0]=1,i=1;i<=100000;i++) power[i]=power[i-1]*BASE;
    for(cin>>n;n;n--)
    {
        scanf("%s",s+1);
        len=strlen(s+1);s[++len]='#';
        for(i=1;i<=len;i++)
            n2[i]=(n2[i-1]*BASE+s[i]);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(i=0;i<cnt;i++)
        {
            if(str[pos[i]]=='*')
            {
                for(j=1;j<=len;j++)
                if(dp[i][j-1]) dp[i][j]=1;
            }
            for(j=0;j<=len;j++)
            if(dp[i][j]&&h1(pos[i]+1,pos[i+1]-1)==h2(j+1,j+pos[i+1]-pos[i]-1))
            {
                if(str[pos[i+1]]=='?') dp[i+1][j+pos[i+1]-pos[i]]=1;
                else dp[i+1][j+pos[i+1]-pos[i]-1]=1;
            }
        }
        if(dp[cnt][len]) puts("YES");
        else puts("NO");
    }
}```