【AHOI2005】【CQOI2014】病毒检测/通配符匹配

Source and Judge

AHOI2005 病毒检测
Bzoj1966
Luogu2536
CQOI2014 通配符匹配
Bzoj3507
Luogu3167

Problem

【Description】
给出通配符字符串,其中 * 的意思是可以匹配上0个或任意多个字符,而 ? 的意思是匹配上任意一个字母,询问给出字符串是否能匹配。
【Input】
如题目描述
【Output】
如题目描述
【Limited conditions】
0<N<100
通配符字符串的长度不超过100000
询问字符串的长度不超过500
通配符个数不超过10
【Sample input 1】

1
2
3
**ASD*ASDASD*A?SD?*AS?D*SAD?A?D*?
1
ASDASDASDADSDASSDASDDDSADAASDAAAAS


【Sample output 1】
0
【Sample input 2】
1
2
3
4
5
6
7
*a*
5
asd
asddd
as
s
sdd


【Sample output 2】
2
【Sample explanation】

Record

10h
话说我的心路历程可真有意思:
ac机=》Here=》贪心
比它还长……虽然都没有打代码233

Analysis

请先思考后再展开

这道题……栋老师跟Claris学,我跟栋老师学……

前置知识:Hash

通配符就是本题最关键的部分
对于星号,连长度都是任意的,是有很高自由度的,也是最高优先级的,所以要以其为分割点分成一个个段。
对于问号,虽然说没有星号这么bt,好歹限制了长度,但其作用并非万能字符那么简单。

咱们先从一些显然的事实开始入手:

  1. 如果没有星号,直接匹配
  2. 对于第一个星号左边的,必须匹配;最后一个星号后面的部分同理
  3. 剩下的段,如果每一个都尽量地偏前面匹配,显然是最优的(或者说,否则不会更优)
    如果不计算匹配的话,以上过程最坏是O(q*星号数量*n)=1kw

然而要怎么匹配呢?
如果可以常数级别那当然是极好的
那验证相同性……当然要祭出hash
不过可别忽略问号哦,所以按照问号拆分开来就好了
因为通配符数量的保证,复杂度是常数级别的。

然后就没有然后了。。。。

Code1

CQOI2014

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=110000;
const int MXCNT=15;
const ull base=13331;
//*******************全局定义*******************
ull bs[MAXN];
char s[MAXN];int ln;
int cnt,pos[MXCNT];
int num[MXCNT],sum[MXCNT][MXCNT];//数量,每个小段数量
ull ha[MXCNT][MXCNT];//每个小段hash值
//*******************实现*******************
bool cmp(char a,char b) {return (a=='?' or b=='?')?1:(a==b);}
ull hb[MAXN];//Hash
ull gethash(int l,int r) { return hb[r]-hb[l-1]*bs[r-l+1]; }
bool check(int k,int l)
{
for(int i=0;i<=num[k-1];i++)
{
if(sum[k-1][i]==0) {l++;continue;}
if(ha[k-1][i]!=gethash(l,l+sum[k-1][i]-1)) return false;
l+=sum[k-1][i]+1;//注意+1,因为问号
}
return true;
}
char s2[MAXN];
bool solve()
{
scanf("%s",s2+1);int ln2=strlen(s2+1);
if(!cnt)//无星号
{
if(ln!=ln2) return false;
for(int i=1;i<=ln;i++) if(!cmp(s[i],s2[i])) return false;
}
else
{
for(int i=1;i<pos[1];i++) if(!cmp(s[i],s2[i])) return false;
for(int i=1;i<=ln-pos[cnt];i++) if(!cmp(s[ln-i+1],s2[ln2-i+1])) return false;
int l=pos[1],r=ln2-(ln-pos[cnt])+1;//对于s2
for(int i=l;i<=r;i++) hb[i]=hb[i-1]*base+s2[i];
for(int k=2;k<=cnt;k++)
{
for(;l<=r;l++) if(check(k,l)) break;
l+=pos[k]-pos[k-1]-1;
if(l>r) return false;
}
}
return true;
}
//*******************主函数*******************
int main()
{
bs[0]=1;for(int i=1;i<MAXN;i++) bs[i]=bs[i-1]*base;
scanf("%s",s+1);ln=strlen(s+1);
cnt=0;
for(int i=1;i<=ln;i++)
if(s[i]=='*') pos[++cnt]=i;
else if(s[i]=='?') ++num[cnt];
else sum[cnt][num[cnt]]++,ha[cnt][num[cnt]]=ha[cnt][num[cnt]]*base+s[i];
int q;scanf("%d",&q);
while(q--) solve()?puts("YES"):puts("NO");
}

Code2

AHOI2005

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=1100;
const int MXCNT=2100;
const ull base=13331;
//*******************全局定义*******************
ull bs[MAXN];
char s[MAXN];int ln;
int cnt,pos[MXCNT];
int num[MXCNT],sum[MXCNT][MXCNT];//数量,每个小段数量
ull ha[MXCNT][MXCNT];//每个小段hash值
//*******************实现*******************
bool cmp(char a,char b) {return (a=='?' or b=='?')?1:(a==b);}
ull hb[MAXN];//前缀Hash
ull gethash(int l,int r) { return hb[r]-hb[l-1]*bs[r-l+1]; }
bool check(int k,int l)
{
for(int i=0;i<=num[k-1];i++)
{
if(sum[k-1][i]==0) {l++;continue;}
if(ha[k-1][i]!=gethash(l,l+sum[k-1][i]-1)) return false;
l+=sum[k-1][i]+1;//注意+1,因为问号
}
return true;
}
char s2[MAXN];
bool solve()
{
scanf("%s",s2+1);int ln2=strlen(s2+1);
if(!cnt)//无星号
{
if(ln!=ln2) return false;
for(int i=1;i<=ln;i++) if(!cmp(s[i],s2[i])) return false;
}
else
{
for(int i=1;i<pos[1];i++) if(!cmp(s[i],s2[i])) return false;
for(int i=1;i<=ln-pos[cnt];i++) if(!cmp(s[ln-i+1],s2[ln2-i+1])) return false;
int l=pos[1],r=ln2-(ln-pos[cnt])+1;//对于s2
for(int i=l;i<=r;i++) hb[i]=hb[i-1]*base+s2[i];
for(int k=2;k<=cnt;k++)
{
for(;l<=r;l++) if(check(k,l)) break;
l+=pos[k]-pos[k-1]-1;
if(l>r) return false;
}
}
return true;
}
//*******************主函数*******************
int main()
{
bs[0]=1;for(int i=1;i<MAXN;i++) bs[i]=bs[i-1]*base;
scanf("%s",s+1);ln=strlen(s+1);
cnt=0;
for(int i=1;i<=ln;i++)
if(s[i]=='*') pos[++cnt]=i;
else if(s[i]=='?') ++num[cnt];
else sum[cnt][num[cnt]]++,ha[cnt][num[cnt]]=ha[cnt][num[cnt]]*base+s[i];
int q;scanf("%d",&q);
int ans=0;
while(q--) ans+=!solve();
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/病毒检测.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%