[关闭]
@ysner 2018-10-15T16:39:46.000000Z 字数 2569 阅读 1678

[CQOI2014]通配符匹配

DP 字符串


题面

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

解析

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

状态显然是表示上面的串匹配到第位,下面的串匹配到第位。

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

这样复杂度就对了,
然后讨论下转移就行。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #include<vector>
  8. #define ll unsigned long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  12. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  13. using namespace std;
  14. const int N=2e5+100;
  15. int n,m,tot,sta[50],top,ans;
  16. ll ht[N],hs[N],jc[N];
  17. char T[N],S[N];
  18. bool f[20][N];
  19. il int gi()
  20. {
  21. re int x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. int main()
  29. {
  30. scanf("%s",T+1);n=strlen(T+1)+1;T[n]='?';
  31. jc[0]=1;fp(i,1,N-100) jc[i]=jc[i-1]*2333;
  32. fp(i,1,n)
  33. {
  34. ht[i]=ht[i-1]*2333+T[i];
  35. if(T[i]=='*'||T[i]=='?') sta[++top]=i;
  36. }
  37. tot=gi();
  38. while(tot--)
  39. {
  40. scanf("%s",S+1);m=strlen(S+1)+1;S[m]='#';
  41. fp(i,1,m) hs[i]=hs[i-1]*2333+S[i];
  42. memset(f,0,sizeof(f));f[0][0]=1;
  43. fp(i,0,top)
  44. {
  45. if(T[sta[i]]=='*') fp(j,1,m) f[i][j]|=f[i][j-1];
  46. fp(j,0,m)
  47. {
  48. if(!f[i][j]) continue;
  49. re int lt=sta[i]+1,rt=sta[i+1]-1,ls=j+1,rs=j+(rt-lt+1);
  50. if(ht[rt]-ht[lt-1]*jc[rt-lt+1]==hs[rs]-hs[ls-1]*jc[rs-ls+1])
  51. f[i+1][rs+(T[sta[i+1]]=='?')]|=f[i][j];
  52. }
  53. }
  54. puts(f[top][m]?"YES":"NO");
  55. }
  56. return 0;
  57. }

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

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #include<vector>
  8. #define ll unsigned long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  12. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  13. using namespace std;
  14. const int N=1005;
  15. int n,m,tot,f[N][N],sta[N],top,jc[N],ans;
  16. ll ht[N],hs[N];
  17. char T[N],S[N];
  18. il int gi()
  19. {
  20. re int x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. int main()
  28. {
  29. scanf("%s",T+1);n=strlen(T+1)+1;T[n]='?';
  30. jc[0]=1;fp(i,1,1000) jc[i]=jc[i-1]*2333;
  31. fp(i,1,n)
  32. {
  33. ht[i]=ht[i-1]*2333+T[i];
  34. if(T[i]=='*'||T[i]=='?') sta[++top]=i;
  35. }
  36. tot=gi();
  37. while(tot--)
  38. {
  39. scanf("%s",S+1);m=strlen(S+1)+1;S[m]='#';
  40. fp(i,1,m) hs[i]=hs[i-1]*2333+S[i];
  41. memset(f,0,sizeof(f));f[0][0]=1;
  42. fp(i,1,top)
  43. {
  44. re int l=sta[i-1]+1,r=sta[i]-1;
  45. fp(j,r-l+1,m)
  46. {
  47. if(ht[r]-ht[l-1]*jc[r-l+1]==hs[j]-hs[j-(r-l+1)]*jc[r-l+1])
  48. f[i][j+(T[sta[i]]=='?')]|=f[i-1][j-(r-l+1)];
  49. }
  50. if(T[sta[i]]=='*') fp(j,1,m) f[i][j]|=f[i][j-1];
  51. }
  52. ans+=1-f[top][m];
  53. }
  54. printf("%d\n",ans);
  55. return 0;
  56. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注