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\n");
else printf("NO\n");
    }
return 0;
}