【CQOI2014】通配符匹配

题目大意：

思路：

dp加上hash优化，先设f[i][j]为做到i个匹配到了j。然后根据星号把一段字符串拆分成很多段，然后转化为hash值，和原串匹配。

程序:

#include<iostream> 
#include<cstdio> 
#include<cstdlib> 
#include<cmath> 
#include<cstring> 
#define F(i,j,n) for(int i=j;i<=n;i++) 
#define D(i,j,n) for(int i=j;i>=n;i--) 
#define ll long long 
#define ull unsigned long long 
#define maxn 100005 
#define base 13131 
using namespace std;  
char ch[maxn],s[maxn];  
int n,len,cnt,pos[15];  
bool f[15][maxn];  
ull n1[maxn],n2[maxn],p[maxn];  
inline ull h1(int st,int ed)  
{  
    if (st>ed) return 0;  
    return n1[ed]-n1[st-1]*p[ed-st+1];  
}  
inline ull h2(int st,int ed)  
{  
    if (st>ed) return 0;  
    return n2[ed]-n2[st-1]*p[ed-st+1];  
}  
int main()  
{ 
    scanf("%s",ch+1);  
    len=strlen(ch+1);  
    F(i,1,len) if (ch[i]<'a'||ch[i]>'z') pos[++cnt]=i;  
    pos[++cnt]=len+1;ch[++len]='?';  
    F(i,1,len) n1[i]=(n1[i-1]*base+ch[i]);  
    p[0]=1;  
    F(i,1,100000) p[i]=p[i-1]*base;  
    scanf("%d",&n);  
    while (n--)  
    {  
        scanf("%s",s+1);  
        len=strlen(s+1);s[++len]='#';  
        F(i,1,len) n2[i]=n2[i-1]*base+s[i];  
        memset(f,0,sizeof(f));  
        f[0][0]=true;  
        F(i,0,cnt-1)  
        {  
            if (ch[pos[i]]=='*')  
            {  
                F(j,1,len) if (f[i][j-1]) f[i][j]=true;  
            }  
            F(j,0,len) if (f[i][j]&&h1(pos[i]+1,pos[i+1]-1)==h2(j+1,j+pos[i+1]-pos[i]-1))  
            {  
                if (ch[pos[i+1]]=='?') f[i+1][j+pos[i+1]-pos[i]]=true;  
                else f[i+1][j+pos[i+1]-pos[i]-1]=true;  
            }  
        }  
        if (f[cnt][len]) puts("YES");  
        else puts("NO");  
    }  
    return 0;  
}