BZOJ3507: [Cqoi2014]通配符匹配

 必须要记住字符串很好卡一不小心就O(n²),别问我为什么这么说.....QAQ

 这题首先满足位数与字母两个限制，那么我们*分大块？分小块，求各块hash值，同时预处理出来每个字符串的前缀hash这样就可以O(1)对比了（千万不要忘记hash字符串对比的功能，我在考试的时候一脑抽就忘了......）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define hash(a) Hash[a+2]
using namespace std;
typedef unsigned long long ULL;
const ULL k=131;
ULL Std[15][15],Hash[100030],tool[100030];
int len,lon[130],l[15][15],z[130],y[130],L,R,lo[130],n;
char s[100030];
bool Over[130];
inline bool blabla(int start,int num)
{
    for(int i=1;i<=Std[num][0];i++)
       if((ULL)(hash(start+l[num][i]-1)-hash(start-1))==(ULL)Std[num][i]*tool[start])
         start+=l[num][i]+1;
       else
         return 0;
    return 1;
}
void pre()
{
    tool[0]=1;
    for(int i=1;i<=100000;i++)tool[i]=tool[i-1]*k;
    scanf("%s",s);
    R=len=strlen(s);
    L=-1;
    Std[0][0]=1;
    Std[1][0]=1;
    for(int i=0;i<len;i++)
    {
      if(s[i]=='*')
      {
        Std[0][0]++;
        Std[Std[0][0]][0]=1;
        continue;
      }
      if(s[i]=='?')
      {
        Std[Std[0][0]][0]++;
        continue;
      }
      Std[Std[0][0]][Std[Std[0][0]][0]]=Std[Std[0][0]][Std[Std[0][0]][0]]+tool[l[Std[0][0]][Std[Std[0][0]][0]]++]*s[i];
    }
    for(int i=1;i<=Std[1][0];i++)
     L+=l[1][i];
    L+=Std[1][0]-1;
    for(int i=1;i<=Std[0][0];i++)
    {
      for(int j=1;j<=Std[i][0];j++)
        lo[i]+=l[i][j];
      lo[i]+=Std[i][0]-1;
    }
    if(Std[0][0]!=1)
    {
      for(int i=1;i<=Std[Std[0][0]][0];i++)
        R-=l[Std[0][0]][i];
      R-=Std[Std[0][0]][0]-1;
    }
}
void work()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
      z[i]=L+1;
      scanf("%s",s);
      lon[i]=strlen(s);
      y[i]=lon[i]-(len-R)-1;
       
      if(z[i]>y[i]+1)
      {
        Over[i]=1;
        continue;
      }
      hash(0)=s[0];
      for(int j=1;j<lon[i];j++)
       hash(j)=hash(j-1)+s[j]*tool[j];
      if(blabla(0,1)==0)
      {
        Over[i]=1;
        continue;
      }
      if(Std[0][0]==1)continue;
      if(blabla(y[i]+1,Std[0][0])==0)
      {
        Over[i]=1;
        continue;
      }
      if(Std[0][0]<=2)continue;
      int had=2;
      for(int j=z[i];j<=y[i];j++)
      {
        if(j+lo[had]-1>y[i])break;
        if(blabla(j,had))
        {
          j+=lo[had]-1;
          had++;
          if(had==Std[0][0])break;
        }
      }
      if(had!=Std[0][0])
       Over[i]=1;
    }
}
void print()
{
   for(int i=1;i<=n;i++)
   {
    if(Over[i])
     printf("NO\n");
    else
     printf("YES\n");
   }
}
int main()
{
    pre();
    work();
    print();
    return 0;
}