# 冬凌

Even the world forsaked you, a contribution won't be forgotten by all

### 题解 P3167 【[CQOI2014]通配符匹配】

posted on 2018-04-23 15:26:38 | under 题解 |

# 思路

## 0x01 KMP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int cmp(char l,char r){
if(l=='?'||r=='?') return 1;
return l==r;
}
void getfail(char s[],int fail[]){
int len=strlen(s),i,j=0;
fail[0]=fail[1]=0;
for(i=1;i<len;i++){
while(j&&!cmp(s[i],s[j])) j=fail[j];
j+=cmp(s[i],s[j]);fail[i+1]=j;
}
}
int match(char b[],char a[],int fail[],int l,int r,int m,int n){
int i,j=0;
for(i=l;i<=r;i++){
while(j&&!cmp(b[j],a[i])) j=fail[j];
j+=cmp(b[j],a[i]);
if(j==m) return i;
}
return -1;
}
void empty(){}
char s[100010],b[15][100010],a[100010];int n,m,cnt,p1,p2,fail[15][100010],tot;
int main(){
scanf("%s",s);int i,j,tmp,Q,k,l,r,ans=0;n=strlen(s);
p1=(s[0]!='*');p2=(s[n-1]!='*');
for(i=0;i<n;i++){
if(s[i]=='*') continue;
j=i;tmp=0;cnt++;b[cnt][tmp]=s[j];
while(s[j+1]!='*'&&j<n) j++,tmp++,b[cnt][tmp]=s[j];
i=j;
}
for(i=1;i<=cnt;i++) getfail(b[i],fail[i]),tot+=strlen(b[i]);
if(cnt==0){
scanf("%d",&Q);
for(j=1;j<=Q;j++){
scanf("%s",a);puts("YES");
}
}
if(cnt==1&&p1&&p2){
scanf("%d",&Q);
for(j=1;j<=Q;j++){
scanf("%s",a);m=strlen(a);
if(m!=strlen(b[1])) continue;
l=match(b[1],a,fail[1],0,m-1,strlen(b[1]),m);
if(l==m-1) puts("YES");
else puts("NO");
}
return 0;
}
scanf("%d",&Q);
for(j=1;j<=Q;j++){
scanf("%s",a);m=strlen(a);bool flag=0;
if(m<tot) goto end;
l=p1*strlen(b[1]);r=m-p2*strlen(b[cnt])-1;
if(p1)
for(i=0;i<strlen(b[1]);i++)
if(!cmp(b[1][i],a[i])) goto end;
if(p2)
for(i=0;i<strlen(b[cnt]);i++)
if(!cmp(b[cnt][i],a[m-strlen(b[cnt])+i])) goto end;
for(k=p1+1;k<=cnt-p2;k++){
l=match(b[k],a,fail[k],l,r,strlen(b[k]),strlen(a));
if(l==-1) goto end;
l++;
}
puts("YES");flag=1;
end:if(!flag) puts("NO");
}
}

bool cmp(char l,char r){//带通配符情况下判断相等
if(l=='?'||r=='?') return 1;
return l==r;
}
j=0;fail[0]=fail[1]=0;//fail就是next
for(i=1;i<len;i++){
while(j&&!cmp(s[i],s[j])) j=fail[j];
j+=cmp(s[i],s[j]);fail[i+1]=j;
}

## 0x02 优化の $KMP$

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fail[15][100010],n,m,cnt=0,jump[15],stl[15];
char b[15][100010],a[100010];
void getfail(char s[],int len){
int i,j=0;fail[cnt][0]=fail[cnt][1]=0;stl[cnt]=len;
for(i=1;i<len;i++){
while(j&&(s[i]!=s[j])) j=fail[cnt][j];
j+=(s[i]==s[j]);fail[cnt][i+1]=j;
}
}
char s[100010];
int main(){
scanf("%s",s);int i,j,len,k,l;m=strlen(s);
for(i=0;i<m;i++){
if(s[i]=='*') continue;
if(s[i]=='?'){jump[cnt]++;continue;}
j=i;cnt++;len=0;
while(s[j]!='*'&&s[j]!='?'&&j<m) b[cnt][len]=s[j],j++,len++;
getfail(b[cnt],len);
i=j;
}
scanf("%d",&n);
for(l=1;l<=n;l++){
scanf("%s",a);len=strlen(a);
i=jump[0];bool flag=1;
for(k=1;k<=cnt;k++){
j=0;
for(;i<len;i++){
while(j&&(a[i]!=b[k][j])) j=fail[k][j];
j+=(a[i]==b[k][j]);
if(j==stl[k]) break;
}
if(j<stl[k]){
puts("NO");flag=0;break;
}
i+=jump[k];
}
if(flag) puts("YES");
}
}

## 0x03 $dp$

$KMP$ 行不通了，我们来想想一个更基础的做法： $dp$

## 0x04 字符串 $hash$

$hash$ 一下！

## 0x05 $hash+$ 前缀和

### $tmp=\sum_{j=0}^ps[j]\ast x^{llen-j}$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll unsigned long long
ll key=19260817ll;//膜法数字
using namespace std;
ll pre[100010],mul[100010],h[20];int n,cnt,sp[20],stl[20],dp[15][100010];
//sp表示通配符类型，stl就是strlen（表示某一段的长度），h是模板串某一段的hash值
char b[15][100010],a[100010],tmp[100010];
ll gethash(char s[],int len){//秦九韶算法求hash
ll re=0;int i;
for(i=0;i<len;i++) re*=key,re+=(ll)s[i];
return re;
}
int main(){
scanf("%s",a);int i,j,k,l,len=strlen(a);ll t1;
mul[0]=1;
for(i=1;i<=100000;i++) mul[i]=mul[i-1]*key;
if(a[0]=='*'||a[0]=='?') h[++cnt]=gethash(b[cnt],stl[cnt]=0);
for(i=0;i<len;){//预处理每一段
if(a[i]=='*'||a[i]=='?'){sp[cnt]=(sp[cnt]||(a[i]=='*'));i++;}
j=0;cnt++;
while(a[i]!='*'&&a[i]!='?'&&i<len) b[cnt][j]=a[i],i++,j++;
h[cnt]=gethash(b[cnt],stl[cnt]=j);
}
len++;
if(a[len-2]=='*'||a[len-2]=='?') cnt++,sp[cnt]=stl[cnt]=h[cnt]=0;
else sp[cnt]=0;
scanf("%d",&n);
for(l=1;l<=n;l++){
memset(a,0,sizeof(a));
scanf("%s",a);a[strlen(a)]='$'; memset(dp,0,sizeof(dp));dp[0][0]=1; len=strlen(a); for(i=0;i<len;i++) pre[i+1]=pre[i]*key+(ll)a[i];//求前缀和 for(j=0;j<=len;j++){ for(i=0;i<=cnt;i++){ if(!dp[i][j]) continue; t1=pre[j+stl[i+1]]-pre[j]*mul[stl[i+1]]; if(t1==h[i+1]){//hash值相等，匹配成功 if(sp[i+1]) for(k=j+stl[i+1];k<=len;k++) dp[i+1][k]=1; else dp[i+1][j+stl[i+1]+1]=1; //这里分情况递推 } } } if(dp[cnt][len]) puts("YES"); else puts("NO"); } }$WTF!!!!!$难道这个算法还是错的？？？？ ## 0x06 最后的优化 不能放弃希望 我们观察写出的代码——没有任何一个地方会造成死循环，那么就是常规循环导致它$TLE$了，究竟是哪一段呢？ if(t1==h[i+1]){ if(sp[i+1]) for(k=j+stl[i+1];k<=len;k++) dp[i+1][k]=1; else dp[i+1][j+stl[i+1]+1]=1; } 没错，正是这个万恶的$for$循环！ 这个$for$循环的作用，是在$sp[i+1]=1$，也就是下一个通配符为'*'的时候，用来一路更新下去的 但是这样更新来更新去，一定会导致$TLE$那我们需要一个优化，让这个循环的过程分散到遍历$dp[i][j]$的时候去，省去一层$n$的复杂度 这里，我们考虑使用不同的值来表示$dp[i][j]$的不同意义： 当$dp[i][j]=-1$的时候，说明这个节点没有访问过，continue 当$dp[i][j]=0$的时候，说明这个节点被且仅被一个'?'往后的递推访问过，这时我们令$dp[i][j]=2,dp[i][j+1]=2$，并continue（因为当前节点并没有意义，只是访问过，不能继续递推） 当$dp[i][j]=1$的时候，说明这个节点是被'*'访问过的，这时我们令$dp[i][j+1]=1$，并且这个点有意义，可以往下递推 当$dp[i][j]=2$的时候，说明这个节点被'?'访问过的节点更新到了2，这时直接从这个节点往后递推，不需要更新值 最后，当$dp[i][j]=3$的时候——这个是一个非常特殊的情况 我们发现，上述的-1到2的值里面，1的优先级最高，0次之，2最低，-1可以被它们随便覆盖 但是我们的确会出现这样的情况：一个0延伸出来的2，覆盖到了另一个0 此时这个0不仅会令$dp[i][j]=dp[i][j+1]=2$，它自身也需要往下递推，而不是直接continue（因为上一个过来的2说明它有这个意义） 所以我们令这种情况下的$dp[i][j]$的值为3，此时令$dp[i][j+1]=2$，并且从当前节点递推 初始化的时候，全部设为-1，$dp[0][0]=2$最后如果dp[模板串的段数][文本串长度]不是-1的话，就输出YES，否则NO 代码如下： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll unsigned long long ll key=19260817ll; using namespace std; ll pre[100010],mul[100010],h[20];int n,cnt,sp[20],stl[20],dp[15][100010]; char b[15][100010],a[100010],tmp[100010]; ll gethash(char s[],int len){ ll re=0;int i; for(i=0;i<len;i++) re*=key,re+=(ll)s[i]; return re; } int main(){ scanf("%s",a);int i,j,k,l,len=strlen(a);ll t1; mul[0]=1; for(i=1;i<=100000;i++) mul[i]=mul[i-1]*key; if(a[0]=='*'||a[0]=='?') h[++cnt]=gethash(b[cnt],stl[cnt]=0); for(i=0;i<len;){ if(a[i]=='*'||a[i]=='?'){sp[cnt]=(sp[cnt]||(a[i]=='*'));i++;} j=0;cnt++; while(a[i]!='*'&&a[i]!='?'&&i<len) b[cnt][j]=a[i],i++,j++; h[cnt]=gethash(b[cnt],stl[cnt]=j); } len++; if(a[len-2]=='*'||a[len-2]=='?') cnt++,sp[cnt]=stl[cnt]=h[cnt]=0; else sp[cnt]=0; scanf("%d",&n); for(l=1;l<=n;l++){ memset(a,0,sizeof(a)); scanf("%s",a); len=strlen(a);a[len]='$';len++;
memset(dp,-1,sizeof(dp));dp[0][0]=2;pre[0]=0;
for(i=0;i<len;i++) pre[i+1]=pre[i]*key+(ll)a[i];
for(j=0;j<=len;j++){
for(i=0;i<=cnt;i++){//只有这里有差别
if(dp[i][j]==-1) continue;
if(dp[i][j]==1) dp[i][j+1]=1;
if(!dp[i][j]){
dp[i][j]=2;
if(dp[i][j+1]==-1) dp[i][j+1]=2;
if(dp[i][j+1]==0) dp[i][j+1]=3;//判断赋2还是3
continue;
}
if(dp[i][j]==3){
dp[i][j]=2;
if(dp[i][j+1]==-1) dp[i][j+1]=2;
if(dp[i][j+1]==0) dp[i][j+1]=3;//判断赋2还是3
}
t1=pre[j+stl[i+1]]-pre[j]*mul[stl[i+1]];
if(t1==h[i+1]){
dp[i+1][j+stl[i+1]]=max(dp[i+1][j+stl[i+1]],sp[i+1]);
}
}
}
if(dp[cnt][len]!=-1) puts("YES");
else puts("NO");
}
}

Finally，这道题目告一段落

# 0x07 总结

The Way To ACCEPTED