[CQOI2014]通配符匹配

DP 字符串

题面

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

• $n\leq100,|S|\leq10^5$
• 通配符个数$\leq10$

解析

由于一些不可言妙的错误，我调这破题的时间跨度长达4h

状态显然是$f[i][j]$表示上面的串匹配到第$i$位，下面的串匹配到第$j$位。

然后注意到上面那串中最值得商榷的是一个通配符匹配哪些字符。
所以可以把上面的串简化为通配符形式，通配符之间的部分用哈希与下面匹配就行。

这样复杂度就对了，$O(n*10|S|)$。
然后讨论下转移就行。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2e5+100;
int n,m,tot,sta[50],top,ans;
ll ht[N],hs[N],jc[N];
char T[N],S[N];
bool f[20][N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  scanf("%s",T+1);n=strlen(T+1)+1;T[n]='?';
  jc[0]=1;fp(i,1,N-100) jc[i]=jc[i-1]*2333;
  fp(i,1,n)
    {
      ht[i]=ht[i-1]*2333+T[i];
      if(T[i]=='*'||T[i]=='?') sta[++top]=i;
    }
  tot=gi();
  while(tot--)
    {
      scanf("%s",S+1);m=strlen(S+1)+1;S[m]='#';
      fp(i,1,m) hs[i]=hs[i-1]*2333+S[i];
      memset(f,0,sizeof(f));f[0][0]=1;
      fp(i,0,top)
        {
      if(T[sta[i]]=='*') fp(j,1,m) f[i][j]|=f[i][j-1];
      fp(j,0,m)
        {
          if(!f[i][j]) continue;
          re int lt=sta[i]+1,rt=sta[i+1]-1,ls=j+1,rs=j+(rt-lt+1);
          if(ht[rt]-ht[lt-1]*jc[rt-lt+1]==hs[rs]-hs[ls-1]*jc[rs-ls+1])
        f[i+1][rs+(T[sta[i+1]]=='?')]|=f[i][j];
        }
    }
      puts(f[top][m]?"YES":"NO");
    }
  return 0;
}

SOS：谁能帮我查下这份代码问题出在哪里。。。(用来交[AHOI2005]病毒检测）

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=1005;
int n,m,tot,f[N][N],sta[N],top,jc[N],ans;
ll ht[N],hs[N];
char T[N],S[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  scanf("%s",T+1);n=strlen(T+1)+1;T[n]='?';
  jc[0]=1;fp(i,1,1000) jc[i]=jc[i-1]*2333;
  fp(i,1,n)
    {
      ht[i]=ht[i-1]*2333+T[i];
      if(T[i]=='*'||T[i]=='?') sta[++top]=i;
    }
  tot=gi();
  while(tot--)
    {
      scanf("%s",S+1);m=strlen(S+1)+1;S[m]='#';
      fp(i,1,m) hs[i]=hs[i-1]*2333+S[i];
      memset(f,0,sizeof(f));f[0][0]=1;
      fp(i,1,top)
        {
       re int l=sta[i-1]+1,r=sta[i]-1;
      fp(j,r-l+1,m)
        {
          if(ht[r]-ht[l-1]*jc[r-l+1]==hs[j]-hs[j-(r-l+1)]*jc[r-l+1])
        f[i][j+(T[sta[i]]=='?')]|=f[i-1][j-(r-l+1)];
        }
      if(T[sta[i]]=='*') fp(j,1,m) f[i][j]|=f[i][j-1];
    }
      ans+=1-f[top][m];
    }
  printf("%d\n",ans);
  return 0;
}