ZR 集训 Day20 - 基础字符串算法

前言 很久没写串串题字符串题了，并且博客上似乎也没有关于字符串的专题，所以今天把一些基础的模板重新打了一遍，放了上来。 题单 CF1200E Compress Words 字符串哈希题。 维护答案串的前缀哈希，对新加入的串做前缀哈希处理，并暴力枚举答案串后缀与新串前缀的重合长度即可。 代码： C++ #include using namespace std; using ll=long long; const int N=1e6+5; const ll p=1e9+7; const int mod=998244353; int T,n,m; ll a[N],b[N],mi[N]; string now="#",s; void init(){ mi[0]=1; for(int i=1;i>T; for(int i=1;i>s; m=s.size(),s="#"+s; solve(); } for(int i=1;i `#include using namespace std; using ll=long long; const int N=1e6+5; const ll p=1e9+7; const int mod=998244353; int T,n,m; ll a[N],b[N],mi[N]; string now="#",s; void init(){ mi[0]=1; for(int i=1;iN;i++) mi[i]=mi[i-1]*p; } void solve(){ int ans=0; for(int i=1;im;i++) b[i]=(b[i-1]*p+s[i])%mod; for(int i=1;imin(n,m);i++){ if(a[n]-a[n-i]*mi[i]==b[i]){ ans=i; } } for(int i=ans+1;im;i++){ a[n+1]=(a[n]*p+s[i])%mod; now+=s[i],n++; } } signed main(){ init(); cin>>T; for(int i=1;iT;i++){ cin>>s; m=s.size(),s="#"+s; solve(); } for(int i=1;in;i++) coutnow[i]; return 0; }` P8306 【模板】字典树 / Trie 字典树模板，用现在的马蜂重写了一遍，封装到结构体里了。 代码： C++ #include using namespace std; const int N=5e6+5; int T,n,q; struct TRIE{ int idx=0; int trie[N][70],tag[N]; int cti(char c){ if(c>='a'&&c='A'&&c>n>>q; while(n--){ cin>>s; trie.insert(s); } while(q--){ cin>>s; cout>T; while(T--) solve(); return 0; } `#include using namespace std; const int N=5e6+5; int T,n,q; struct TRIE{ int idx=0; int trie[N][70],tag[N]; int cti(char c){ if(c>='a'&&c'z') return c-'a'; else if(c>='A'&&c'Z') return c-'A'+26; else return c-'0'+52; } void clear(){ for(int i=0;iidx;i++) { memset(trie[i],0,sizeof trie[i]); tag[i]=0; } idx=0; } void insert(string s){ int p=0; for(int i=0;is.size();i++){ if(!trie[p][cti(s[i])]) trie[p][cti(s[i])]=++idx; p=trie[p][cti(s[i])],tag[p]++; } } int check(string s){ int p=0; for(int i=0;is.size();i++){ if(!trie[p][cti(s[i])]) return 0; p=trie[p][cti(s[i])]; } return tag[p]; } }trie; void solve(){ trie.clear(); string s; cin>>n>>q; while(n--){ cin>>s; trie.insert(s); } while(q--){ cin>>s; couttrie.check(s)"\n"; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; while(T--) solve(); return 0; }` P3375 【模板】KMP 也是找到了一个非常简洁的写法，看代码： C++ #include using namespace std; const int N=2e6+5; int n,m; int pi[N]; string a,b; void getpi(){ for(int i=1;i0&&a[i]!=a[j]) j=pi[j-1]; if(a[i]==a[j]) j++; pi[i]=j; } } int main(){ cin>>b>>a; n=a.size(),m=b.size(); a=a+"#"+b; getpi(); for(int i=n+1;i `#include using namespace std; const int N=2e6+5; int n,m; int pi[N]; string a,b; void getpi(){ for(int i=1;ia.size();i++){ int j=pi[i-1]; while(j>0&&a[i]!=a[j]) j=pi[j-1]; if(a[i]==a[j]) j++; pi[i]=j; } } int main(){ cin>>b>>a; n=a.size(),m=b.size(); a=a+"#"+b; getpi(); for(int i=n+1;in+m;i++) if(pi[i]==n) couti-2*n+1"\n"; for(int i=0;in;i++) coutpi[i]" "; return 0; }` P13270 【模板】最小表示法 简化题意：把一个字符串首位相连得到一个环，再把这个环从一处断开得到一个新的字符串，求可能得到的新字符串中字典序最小的那一个。 详细步骤看代码中的注释： C++ #include using namespace std; int zxbsf(int n,string s){ int i=0,j=1,k=0;//维护 i,j 两个指针以及当前匹配长度 k while(is[(j+k)%n]) i+=k+1,k=0;//如果 j 指针更优，则把 i 移到失配位置的后一位，保证最优解 else if(s[(i+k)%n]>n>>s; int id=zxbsf(n,s); for(int i=0;i `#include using namespace std; int zxbsf(int n,string s){ int i=0,j=1,k=0;//维护 i,j 两个指针以及当前匹配长度 k while(in&&jn&&kn){//保证不越界 if(i==j) j++;//如果指针重合，则避让 if(s[(i+k)%n]>s[(j+k)%n]) i+=k+1,k=0;//如果 j 指针更优，则把 i 移到失配位置的后一位，保证最优解 else if(s[(i+k)%n]s[(j+k)%n]) j+=k+1,k=0;//同理 else k++;//否则继续匹配 } return min(i,j);//最后指针最小的那一个就是答案 } int main(){ int n; string s; cin>>n>>s; int id=zxbsf(n,s); for(int i=0;in;i++) couts[(i+id)%n]; return 0; }` P3805 【模板】Manacher 做过的板子题，在相邻字符中间添加辅助字符的思路非常妙。 大致思路：用一个数组记录以当前点为对称中心的最大对称半径，并记录目前右端点最大的回文子串，枚举对称中心，如果当前对称中心在记录的回文子串内，就可以用对称过去的那个点来更新当前这个点，但是要注意如果对称过去那个点的半径对称过来超出了右端点，我们要截断这部分。 代码： C++ #include using namespace std; const int N=3e7+5; int d[N]; int manacher(int n,string s){ int res=-1; string a="!"; for(int i=0;ir) r=i+d[i]-1,l=i-d[i]+1; } for(int i=1;i>s; int n=s.size(); cout `#include using namespace std; const int N=3e7+5; int d[N]; int manacher(int n,string s){ int res=-1; string a="!"; for(int i=0;in;i++) a+="#",a+=s[i]; a+="#$"; n=(n1)+1; d[1]=1; for(int i=2,l=1,r=1;in;i++){ if(ir) d[i]=min(d[l+r-i],1+r-i); while(a[i-d[i]]==a[i+d[i]]) d[i]++; if(i+d[i]-1>r) r=i+d[i]-1,l=i-d[i]+1; } for(int i=1;in;i++) res=max(res,d[i]-1); return res; } int main(){ string s; cin>>s; int n=s.size(); coutmanacher(n,s); return 0; }` P5410 【模板】扩展 KMP / exKMP（Z 函数） 虽然叫扩展 KMP，但是这个算法却和 Manacher 有异曲同工之妙。 算法的核心在于求出 Z 函数，而 Z(i) 表示 s[0,n-1] 与 s[i,n-1] 的最长公共前缀。 考虑维护目前所有 Z 函数前缀区间中右端点最大的那一个区间的左右端点 l,r，并枚举 i，考虑如下几种情况： 若 i\le r，由 Z 函数的性质（s[0,l-r]=s[l,r]）可以知道：s[i,r]=s[i-l,r-l]。那就有 Z(i)\ge \min(Z(i-l),r-i+1)。（注：这里与 r-l+1 取最小值的目的和马拉车算法中一样，对右端点以外的我们并不清楚，所以需要重新计算。）此时又需要分类讨论： - 若 Z(i-l) r，同样暴力即可。 做完以上操作后，更新最 l,r 即可。 代码： C++ #include using namespace std; using ll=long long; const int N=4e7+5; int z[N]; void getz(int n,string s){ for(int i=1,l=0,r=0;ir) r=i+z[i]-1,l=i; } } int main(){ int n,m; ll ans1=0,ans2=0; string a,b; cin>>b>>a; n=a.size(),m=b.size(); a=a+"#"+b; getz(n+m+1,a); for(int i=0;in) ans2^=(ll)(i-n)*(ll)(z[i]+1); } cout `#include using namespace std; using ll=long long; const int N=4e7+5; int z[N]; void getz(int n,string s){ for(int i=1,l=0,r=0;in;i++){ if(ir&&z[i-l]r-i+1) z[i]=z[i-l]; else{ z[i]=max(r-i+1,0); while(z[i]+in&&s[z[i]+i]==s[z[i]]) z[i]++; } if(i+z[i]-1>r) r=i+z[i]-1,l=i; } } int main(){ int n,m; ll ans1=0,ans2=0; string a,b; cin>>b>>a; n=a.size(),m=b.size(); a=a+"#"+b; getz(n+m+1,a); for(int i=0;in+m;i++){ if(i==0) ans1^=(ll)(n+1); else if(in) ans1^=(ll)(i+1)*(ll)(z[i]+1); else if(i>n) ans2^=(ll)(i-n)*(ll)(z[i]+1); } coutans1"\n"ans2; return 0; }` P2375 [NOI2014] 动物园 这个昨天写了一版很详细的，但是忘记保存了，懒得写详细了。。。 考虑枚举所有对 sum_j 产生贡献的后缀 s[i,j] 的 i，不难发现求出 Z 函数后，i 作为左端点所能产生贡献的右端点的区间就可以表示了，差分即可。 代码： C++ #include using namespace std; using ll=long long; const int N=4e7+5; const int mod=1e9+7; vector getz(int n,string s){ vector z(n,0); for(int i=1,l=0,r=0;ir) r=i+z[i]-1,l=i; } return z; } int main(){ int T; cin>>T; while(T--){ int n; ll ans=1; string s; cin>>s; n=s.size(); vector sum(n,0),z=getz(n,s); for(int i=0;i `#include using namespace std; using ll=long long; const int N=4e7+5; const int mod=1e9+7; vectorint> getz(int n,string s){ vectorint> z(n,0); for(int i=1,l=0,r=0;in;i++){ if(ir&&z[i-l]r-i+1) z[i]=z[i-l]; else{ z[i]=max(r-i+1,0); while(z[i]+in&&s[z[i]+i]==s[z[i]]) z[i]++; } if(i+z[i]-1>r) r=i+z[i]-1,l=i; } return z; } int main(){ int T; cin>>T; while(T--){ int n; ll ans=1; string s; cin>>s; n=s.size(); vectorint> sum(n,0),z=getz(n,s); for(int i=0;in;i++){ int len=min(z[i],i); sum[i]++; if(i+lenn) sum[i+len]--; } for(int i=0;in;i++){ if(i) sum[i]+=sum[i-1]; ans=(ans*(sum[i]+1))%mod; } coutans"\n"; } return 0; }`