bzoj3507: [Cqoi2014]通配符匹配

这题一眼看上去像是KMP。。。莫名旁边的zzz说是ACMachine，而且是真的有dalao用这个做。。。

然后呢经过%羊神的题解呢，发现居然是DP+hash字符串比较，但是时间复杂度就很差了（rank倒数第3，还是无法慢过羊神，果然是神一样的男人），不过又学到了有用的东西。

具体hash就是看作一个x进制的数，然后求值取mod（rp不好那也没办法了），然后观察到通配符很小，f[i][j]就是表示枚举到第i通配符，枚举到b串第j个位置，可不可以匹配。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int mod=1000000007;
LL cf[110000];

char sa[110000],sb[110000];
int pos[110000],plen;

LL ha[110000],hb[110000];
LL HASH(LL *h,int x,int y)
{
    return (h[y]-(h[x-1]*cf[y-x+1])%mod+mod)%mod;
}

bool f[20][110000];
int main()
{
    cf[1]=31;for(int i=2;i<=100000;i++)cf[i]=(cf[i-1]*31)%mod;
    
    
    scanf("%s",sa+1);int alen=strlen(sa+1);
    sa[++alen]='?';
    
    ha[0]=0;plen=0;
    for(int i=1;i<=alen;i++)
        if(sa[i]>='a'&&sa[i]<='z')
            ha[i]=((ha[i-1]*31)%mod+(sa[i]-'a'+1))%mod;
        else
            ha[i]=((ha[i-1]*31)%mod+27)%mod, pos[++plen]=i;
    
    
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",sb+1);int blen=strlen(sb+1);
        sb[++blen]='?';
        
        hb[0]=0;
        for(int i=1;i<=blen;i++)
            hb[i]=((hb[i-1]*31)%mod+(sb[i]-'a'+1))%mod;
        
        
        memset(f,false,sizeof(f));f[0][0]=true;
        for(int i=1;i<=plen;i++)
        {
            int pl=pos[i-1]+1,pr=pos[i]-1;
            int L=pr-pl+1;
            if(sa[pos[i]]=='*')
            {
                for(int j=L+1;j<=blen;j++)
                {
                    int l=(j-L+1)-1,r=j-1;
                    if(f[i-1][l-1]==true)
                        if(pos[i]==pos[i-1]+1||HASH(ha,pl,pr)==HASH(hb,l,r))
                        {
                            for(int k=j-1;k<=blen;k++)f[i][k]=true;
                            break;
                        }
                }
            }
            else
            {
                for(int j=L+1;j<=blen;j++)
                {
                    int l=(j-L+1)-1,r=j-1;
                    if(f[i-1][l-1]==true)
                        if(pos[i]==pos[i-1]+1||HASH(ha,pl,pr)==HASH(hb,l,r))f[i][j]=true;
                }
            }
        }
        if(f[plen][blen]==true)printf("YES
");
        else printf("NO
");
    }
    return 0;
}