【BZOJ3507【CQOI】通配符匹配DP+Hash
hash DP   发布于 2017-01-08   198人围观  0条评论
hash DP   发表于 2017-01-08   198人围观  0条评论

题目描述

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

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。
第二行包含一个整数n,表示文件个数。
接下来n行,每行为一个仅包含小写字母字符串,表示文件名列表。

输出格式

输出n行,每行为“YES”或“NO”,表示对应文件能否被通配符匹配。

样例输入

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

样例输出

YES
YES
YES
YES
YES
NO

数据范围及提示

对于100%的数据

·字符串长度不超过1 00000

· 1 <=n<=100

·通配符个数不超过10

题解

DP+Hash(刚学Hash)
f[i][j]表示第i个通配符能否匹配到第j个位置。
因为一个*会把字符串分成两段,所以这个*分开的两边一定是要求一样的,这里可以利用hash判断。
然后我们就可以得到通配符串被*分成好几段,这样就可以得到转移。
枚举起点,如果可以匹配就可以转移。
有一些比较方便的处理,比如S最后加一个?,以及s最后加任意一个字符
这样的时间复杂度封顶大概是O(N*k*len),所以一开始自己想到了但是没敢写,但是发现这个转移其实时间复杂度是不满的,所以可以AC
%%%DaD3zZ

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxn = 100010;
const int base = 131;
char S[maxn],s[maxn];
ull hash[2][maxn],bin[maxn];
int p[20],t,n;
bool f[12][maxn];
inline void hash_table(char str[],int opt){
    int len = strlen(str+1);
    for (int i = 1;i <= len;i++) hash[opt][i] = hash[opt][i-1]*base+str[i];
}
inline ull gethash(int l,int r,int opt){
    return r > l ? hash[opt][r]-hash[opt][l-1]*bin[r-l+1] : -1;
}
int main(){
    bin[0] = 1;
    for(int i = 1;i <= maxn-1;++i)
        bin[i] = bin[i-1] * base;
    scanf("%s",S+1);
    hash_table(S,0);
    int len = strlen(S+1);
    for(int i = 1;i <= len;++i)
        if(S[i] == '*' || S[i] == '?')p[++t] = i;
    p[++t] = ++len;
    S[len] = '?';
    scanf("%d",&n);
    while(n--){
        scanf("%s",s+1);
        hash_table(s,1);
        memset(f,0,sizeof(f));
        f[0][0] = 1;
        int len = strlen(s+1); s[++len] = '@';
        for(int i = 0;i <= t-1;++i){
            if(S[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] && gethash(j+1,j+(p[i+1]-1)-(p[i]+1)+1,1) == gethash(p[i]+1,p[i+1]-1,0)){
                    if(S[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[t][len])printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
​

上一篇: [Zjoi2013]K大数查询

下一篇: 【ZJOI2007】【BZOJ1058】报表统计splay+线段树

立即登录,发表评论
没有帐号?立即注册
0 条评论