Codeforce 535 D. Tavas and Malekas 解析(字串匹配)
今天我們來看看CF535D
題目連結
題目
給你一個字串$p$和一些$index$代表字串$p$在哪些位置會和長度為$n$的字串$s$匹配，求有多少種$s$的可能性。
前言
我還是只會$hash$
<div class=“VVVcopyrightAAA”;>@copyright petjelinux 版權所有<br>
<a href=“https://www.cnblogs.com/petjelinux/”>觀看更多正版原始文章請至petjelinux的blog</a></div>
想法
$p$沒有覆蓋到的$index$數量記做$cnt$，如果那些會重疊的$p$沒有矛盾的話，那答案就是$26^{cnt}$，因為有$cnt$的格子都是完全自由的。
這題有三種作法，都是要判斷重疊的$p$有沒有矛盾。注意，我們每次判斷一個從$y[i]$開始的$p$字串有沒有和前面重疊時，只需要和從$y[i-1]$開始的$p$字串比較就好，畢竟如果$y[i-2]$開始的$p$字串和$y[i-1]$開始的$p$字串沒有矛盾的話，那麼$y[i-2]$開始的$p$字串和$y[i]$開始的$p$字串就不會有矛盾(如果$y[i-1]$開始的字串和$y[i]$開始的字串沒有矛盾)。
三種匹配字串的方式是:
- Rolling hash，直接比對子字串的hash值看看一不一樣。
- KMP，只需要維護失敗函數，由於失敗函數代表一個最長的前綴的長度使得在$j-1$結束的字串的後綴和前綴一樣，那麼我們只要看看$p$字串的重疊部分是否沒有矛盾就好。
- Z-Algorithm，和KMP如出一轍，只不過這次$Z$函數代表從$j$開始往後的字串和整個字串的最長前綴長度。一樣只要看看$p$字串的重疊部分是否沒有矛盾就好。
程式碼(Rolling hash):
const int _n=1e6+10;
int t,n,m;
const int _N = _n; // str len
const int _p1 = 31, _M = 1000000009;
int pnM[_N] = {0}; // p^n mod M
int hp[_N] = {0}; // hash prefix
char p[_N];
int lenp,y[_n];
inline void genpnM() {
int res = 1; //p^0%M
pnM[0] = 1;
for (int i = 1; i < _N; i++) pnM[i] = res = (res * 1ll * _p1) % _M;
}
inline void genhp() { //hp[n]=hash prefix[0,n)
int res = 0;
hp[0] = 0; //[0,0) is empty string
for (int i = 1; i <= lenp; i++) hp[i] = res = (res * 1ll * _p1 + p[i - 1] * 1ll) % _M;
}
inline int dhash(char s[]) { //direct hash
int len = strlen(s);
int res = 0;
for (int i = 1; i <= len; i++) res = (res * 1ll * _p1 + s[i - 1] * 1ll) % _M;
return res;
}
inline int hashlr(int l, int r) { //[l,r)
int tmp = hp[r] * 1ll - pnM[r - l] * 1ll * hp[l] % _M;
if (tmp < 0) tmp += _M;
return tmp;
}
//以上是rolling hash模板
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>p;lenp=strlen(p);rep(i,0,m){cin>>y[i];y[i]--;}
genpnM();genhp();
int cnt=y[0];rep(i,1,m){
if(y[i-1]+lenp-1>=y[i]){
if(hashlr(y[i]-y[i-1],lenp)!=hashlr(0,lenp-(y[i]-y[i-1]))){
cout<<0<<'\n';return 0;
}
}
else cnt+=y[i]-(y[i-1]+lenp-1)-1;
}cnt+=n-(y[m-1]+lenp);
if(m==0)cnt=n;
cout<<powmod(26,cnt)<<'\n';
return 0;
}
標頭、模板請點Submission看
Submission
程式碼(KMP):
const int _n=1e6+10;
int t,n,m;
char p[_n];
int lenp,y[_n],jj,F[_n];
bool vis[_n];
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>p;lenp=strlen(p);rep(i,0,m){cin>>y[i];y[i]--;}
/*F[0]=-1,jj=-1;rep(i,0,lenp){
jj=F[i];
while(jj!=-1 and p[i]!=p[jj])jj=F[jj];
F[i+1]=jj+1; //if jj==-1, F[i]=0
}*/ //也行
F[0]=-1;
for(int i = 0, j = -1; i < lenp; F[++i] = ++j) { //計算失敗函數，一般來說i<lenp-1，但是這題我們需要i<lenp
while (j != -1 && p[i] != p[j]) j = F[j];
}
jj=F[lenp];
while(jj!=-1){ //看看哪些前綴可以和整條字串p的後綴匹配
vis[jj]=1;
jj=F[jj];
}
int cnt=y[0];rep(i,1,m){
if(y[i-1]+lenp-1>=y[i]){
if(!vis[lenp-(y[i]-y[i-1])]){
cout<<0<<'\n';return 0;
}
}
else cnt+=y[i]-(y[i-1]+lenp-1)-1;
}cnt+=n-(y[m-1]+lenp);
if(m==0)cnt=n;
cout<<powmod(26,cnt)<<'\n';
return 0;
}
標頭、模板請點Submission看
Submission
程式碼(Z-Algorithm):
const int _n=1e6+10;
int t,n,m,lenp,Z[_n],y[_n];
char p[_n];
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>p;lenp=strlen(p);rep(i,0,m){cin>>y[i];y[i]--;}
int L = 0, R = 0;
for (int i = 1; i < lenp; i++) {
if (i > R) {
L = R = i;
while (R < n && p[R-L] == p[R]) R++;
Z[i] = R-L; R--;
} else {
int k = i-L;
if (Z[k] < R-i+1) Z[i] = Z[k];
else {
L = i;
while (R < n && p[R-L] == p[R]) R++;
Z[i] = R-L; R--;
}
}
}
int cnt=y[0];rep(i,1,m){
if(y[i-1]+lenp-1>=y[i]){
if(Z[y[i]-y[i-1]]!=lenp-(y[i]-y[i-1])){
cout<<0<<'\n';return 0;
}
}
else cnt+=y[i]-(y[i-1]+lenp-1)-1;
}cnt+=n-(y[m-1]+lenp);
if(m==0)cnt=n;
cout<<powmod(26,cnt)<<'\n';
return 0;
}
標頭、模板請點Submission看
Submission