https://www.zybuluo.com/ysner/note/1311407
题面
几乎所有操作系统的命令行界面((CLI))中都支持文件名的通配符匹配以方便用户。
最常见的通配符有两个，一个是星号，可以匹配(0)个及以上的任意字符；
另一个是问号，可以匹配恰好一个任意字符。
现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。
- (nleq100,|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
",ans);
return 0;
}