「題解報告」 P3167 [CQOI2014]通配符匹配
思路
*和?顯然無法直接匹配，但是可以發現「通配符個數不超過 \(10\) 」，那么我們可以考慮分段匹配，
我們首先把原字串分成多個以一個通配符開頭的字串，如將 happy*birthdey?xingchen 分成：
happy
*birthday
?xingchen
然后設原串有 \(m\) 個通配符， \(op_i\) 表示分出來的第 \(i\) 個串前的通配符（\(0\) 沒有，\(1\) 是?，\(2\) 是*），\(len_i\) 表示分出來的第 \(i\) 個串的長度，\(f_{i,j}\) 表示分出來的第 \(i\) 個串的結尾能否匹配上當前查詢的字串的位置 \(j\)，
則轉移方程顯然為：
\[f_{i,j}= \begin{cases} f_{i-1,j-len_i}&op_i=0\\ f_{i-1,j-len_i-1}&op_i=1\\ \sum_{k=0}^{j-len}f_{i-1,j-len_i}&op_i=2\\ \end{cases} \]能否轉移直接用 Hash \(\Theta(1)\) 比較即可，
初始狀態 \(f_{0,0}=1\)，答案為 \(f_{m,\left|S\right|}\)，時間復雜度 \(\Theta(mn\left|S\right|)\)，
代碼
const ll N=1e5+10,inf=1ll<<40;
ll T,n,m=1,ln,ans;
ll a1[20],a2[20],len[20],op[20];
ll f[20][N],sm[N];
char s[N],t[N];
class Hash{
public:
const ll P1=315716521,P2=475262633;
ll h1[N],h2[N],z1[N],z2[N];
inline void Init(char *s){
z1[0]=z2[0]=1;
ll length=strlen(s+1);
_for(i,1,length){
z1[i]=z1[i-1]*233%P1;
z2[i]=z2[i-1]*233%P2;
h1[i]=(h1[i-1]*233+s[i]-'a'+1)%P1;
h2[i]=(h2[i-1]*233+s[i]-'a'+1)%P2;
}
return;
}
inline ll GetHash1(ll l,ll r){return (h1[r]-h1[l-1]*z1[r-l+1]%P1+P1)%P1;}
inline ll GetHash2(ll l,ll r){return (h2[r]-h2[l-1]*z2[r-l+1]%P2+P2)%P2;}
}b;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline ll GetA1(char *awa){
ll hash_val=0;
ll length=strlen(awa+1);
_for(i,1,length)hash_val=(hash_val*233+awa[i]-'a'+1)%b.P1;
return hash_val;
}
inline ll GetA2(char *awa){
ll hash_val=0;
ll length=strlen(awa+1);
_for(i,1,length)hash_val=(hash_val*233+awa[i]-'a'+1)%b.P2;
return hash_val;
}
inline void Pre(){
char qwq[N];
_for(i,1,n){
if(s[i]=='?'||s[i]=='*'){
if(i==1)--m;
a1[m]=GetA1(qwq);
a2[m]=GetA2(qwq);
memset(qwq,0,sizeof(qwq));
op[++m]=(s[i]=='?')?1:2;
}
else qwq[++len[m]]=s[i];
}
a1[m]=GetA1(qwq);
a2[m]=GetA2(qwq);
return;
}
inline bool Check(ll a,ll i){
if(a1[a]!=b.GetHash1(i-len[a]+1,i))return 0;
if(a2[a]!=b.GetHash2(i-len[a]+1,i))return 0;
return 1;
}
inline void PP(){
f[0][0]=1;
_for(i,0,ln)sm[i]=1;
_for(i,1,m){
_for(j,0,ln)f[i][j]=0;
for_(j,ln,len[i]){
if(Check(i,j)){
if(op[i]==0)f[i][j]=f[i-1][j-len[i]];
else if(op[i]==1)f[i][j]=f[i-1][j-len[i]-1];
else f[i][j]=sm[j-len[i]];
}
}
sm[0]=0;
_for(j,1,ln)sm[j]=sm[j-1]|f[i][j];
}
return;
}
inline void In(){
scanf("%s",s+1);
n=strlen(s+1),Pre();
T=rnt();
while(T--){
scanf("%s",t+1);
b.Init(t),ln=strlen(t+1);
PP(),puts(f[m][ln]?"YES":"NO");
}
return;
}
}
本文來自博客園，作者：Keven-He，轉載請注明原文鏈接：https://www.cnblogs.com/Keven-He/p/16578002.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501624.html
標籤：其他
上一篇：多人同時訪問同一臺電腦怎么實作