字符串学习笔记1

Manacher它是干什么的他是用来匹配回文串的顾名思义就是用的时间复杂度匹配出最长回文串。它怎么做的暴力首先我们知道暴力的写法就是用的时间复杂度从每个节点暴力向外扩张Manacher 解决的就是避免重复。正解核心思想是利用回文的对称性避免重复计算。可以处理奇回文和偶回文通过插入分隔符统一处理。1. 在字符串每两个字符之间及两端插入特殊字符如 #将奇偶回文统一为奇回文。统一为奇回文为的是方便计算因为偶回文不太好统计。2. 维护当前最右回文的中心和右边界。3. 对于位置若则利用对称位置的信息初始化。4. 暴力扩展求出的最长回文半径。5. 更新和。正确性设当前最右回文为以为中心右边界为的回文。对于位置设为关于的对称点。如果以为中心的回文完全包含在以为中心的回文中。由对称性以为中心的回文长度与以为中心相同。故。如果以为中心的回文超出以为中心的回文范围。由对称性范围内的回文是确定的。但r 右侧的字符未知需要暴力扩展。故需要继续扩展。初始化恰好覆盖了这两种情况。由于扩张时只会扩张次所以时间复杂度是。codevoid manacher(){ nstrlen(s1); int m0; t[m]$; for(int i1;in;i) t[m]s[i],t[m]$;\\插入特殊字符 int M0,R0; for(int i1;im;i){ if(iR) p[i]1; else p[i]min(p[2*M-i],R-i1);\\初始化 while(i-p[i]0ip[i]mt[i-p[i]]t[ip[i]]) p[i];\\暴力扩张统计答案 if(ip[i]-1R) Mi,Rip[i]-1;\\更新数值 } int ans0; for(int i1;im;i) ansmax(ans,p[i]);\\统计最大回文串 printf(%d,ans-1); }题目P1659 [国家集训队] 拉拉队排练P4555 [国家集训队] 最长双回文串P1659由题意可知显然每一个和谐群体就是一个长度为奇数的回文串。用 Manacher 可以求每个位置的回文半径。因为我们只要求奇数个的回文串那么显然我们不需要在字符串里添加一些无关字符。那么我们用Manacher求出以当前位置为中心的最长回文子串长度。所以我们就会在求的同时搞出最长的。然后根据对称性可知也有长为的回文子串接着我们只需要统计一下就可以了。注意我们只要奇数个去掉偶数个。因为数据范围过大所以我们要快速幂使得不会爆掉。codeint main(){ scanf(%d%d%s,n,k,s1),lenn,manacher(); for(int in;i;i--) { if(i%20) continue; sumcnt[i]; if(ksum) ans(ans*quickpow(i,sum))%P,k-sum;\\如果你很聪明你会把quickpow的值开_____否则你只有 15 pts。 else{ ans(ans*quickpow(i,k))%P,k-sum; break; } } if(k0) ans-1; coutans; }P4555就直接维护一个表示从出发往前的回文串最大长度维护一个表示从出发往后的回文串最大长度统计答案时直接把每个位置上的答案取最大值即可。codevoid manacher(){ int m0,M0,R0; nstrlen(s1),t[m]$,t[0]; for(int i1;in;i) t[m]s[i],t[m]$; for(int i1;im;i){ if(iR) p[i]min(p[2*M-i],R-i1); else p[i]1; while(t[i-p[i]]t[ip[i]]) p[i]; if(ip[i]-1R) Mi,Rip[i]-1; l[ip[i]-1]max(l[ip[i]-1],p[i]-1); r[i-p[i]1]max(r[i-p[i]1],p[i]-1); } for(int i3;im;i2) r[i]max(r[i],r[i-2]-2); for(int im;i3;i-2) l[i]max(l[i],l[i2]-2); int ans0; for(int i3;im;i2) if(r[i]l[i]) ansmax(ans,l[i]r[i]); coutans; }如果你 WA on #12#13可以看看这个帖子。KMP我已经发过一遍博文了详见这里。exKMP(Z函数)它是干什么的能在的时间内处理出文本串的所有后缀和模式串的最长公共前缀。其中和分别表示和的长度。它怎么做的暴力你就要用的时间复杂度依次枚举。正解我们首先称最长公共前缀的前面部分为前半段后面部分为后半段。以abcabc为例当时abcabc前半段为第 1,2,3 个字符组成的abc后半段为第 4,5,6 个字符组成的abc。我们记录下为使得后端右端点最右的。最长公共前缀是有对称性的。如上例abcabc1 对应 42 对应 53 对应 6。假设 d 的最右端点大于等于我们找到此时的对应点此时若的后半段右端点已经超过前半段的右端点此时我们无法利用全部部分只能利用这一段部分的相等性。此时令。若后半段右端点未超过前半段的右端点则可以直接令。然后我们暴力扩展至无法计算结束。所以本算法其实只有三步根据当前得到一部分长度。暴力扩展得到​。更新。正确性每次暴力扩展必会引起最右端点的右移没有引起右移则只会操作 1 次因此时间复杂度。模板题code:void Z(){ int l0,r0; z[1]m; for(int i2;im;i){ if(irz[i-l1]r-i1) z[i]z[i-l1]; else{ z[i]max(0ll,r-i1); while(iz[i]mb[z[i]1]b[iz[i]]) z[i]; } if(iz[i]-1r) li,riz[i]-1; } } void work(){ int l0,r0; for(int i1;in;i){ if(irz[i-l1]r-i1) p[i]z[i-l1]; else{ p[i]max(0ll,r-i1); while(ip[i]np[i]mb[p[i]1]a[ip[i]])//如果你是 7 pts 那么有可能是这打错了 p[i]; } if(ip[i]-1r) li,rip[i]-1; } } signed main(){ cin(a1)(b1),nstrlen(a1),mstrlen(b1),Z(),work(); for(int i1;im;i) ans^1ll*i*(z[i]1); coutansendl,ans0; for(int i1;in;i) ans^1ll*i*(p[i]1); coutans;//十年OI一场空不开_____见祖宗 }题目P2375CF526DP2375我们用 Z 函数求出每个后缀与原串的然后很轻松的利用差分统计答案即可。Z 函数可以在O(N)的时间内求出每个后缀与原串的他类似于马拉车算法也是递推地求解。假设我们要求第个后缀的我们已经求出来前个维护匹配一个最右端的指针记此时的后缀为原串为。是那么我们可以发现i如果位于的左面的话我们可以利用之前的结果更新当前的然后再暴力扩展随时更新一下指针和 Manacher 其实是一个道理。void solve(){ memset(lcp,0,sizeof lcp),memset(t,0,sizeof t),posr0,ans1,cin(s1),lenstrlen(s1); for(int i2;ilen;i){ if(pos0){ int p1; while(s[plcp[i]]s[ilcp[i]]) lcp[i]; if(lcp[i]) rilcp[i]-1,posi; continue; } if(ir){ int p1; while(s[plcp[i]]s[ilcp[i]]) lcp[i]; if(lcp[i]) rilcp[i]-1,posi; continue; } int nposi-pos1; lcp[i]min(lcp[npos],r-i1); while(s[lcp[i]1]s[ilcp[i]]) lcp[i]; if(ilcp[i]-1r) rilcp[i]-1,posi; } for(int i2;ilen;i) if(lcp[i]) t[i],t[min(2*(i-1),min(len,ilcp[i]-1))1]--; for(int i1;ilen;i) t[i]t[i-1]; for(int i1;ilen;i) ansans*(t[i]1)%mod; coutansendl; }CF526D这道题我们可以利用 KMP 的性质来做我们直接上推算过程首先我们可以把 AB 分为名为 C 的一组那么字符串可以变成 CC...CA其中 C 有个且 A 是 C 的前缀由定义而知。求数组来扫一遍。首先在第一个 C 内所指向的都是最开始的地方。第一个 C 结束的地方为临界点。当扫到第二个 C 的时候所指向的刚好是第一个 C 里的相同位置。第二个 C 扫描结束后所指向的刚好扫完第一个 C。以此类推后面每次扫到的都是上一个 C 内的相同位置。扫到最后一个点也就是最后的 A 结束时它指向了最后一个 C 内的同一位置。我们可以通过最后一个点和它的指向的地方相减得到 C 的长度再通过总长和 C 的长度确定 C 的个数和 A 的长度只要段数是 k 且 A 的长度在 C 以内就可以了。但是我们的段数是大于的本来是有解我们的程序把它判定为无解了。怎么办呢我们可以先把它原本多少段先求出来然后看看究竟是 C 的数量除以大还是模大就可以判断了。codewhile(in){ if(j-1||s[i1]s[j1]) i,j,nxt[i]j; else jnxt[j]; } for(int i1;in;i){ pi-nxt[i],hi/p; if(i%p) cout((h/m-h%m)0); else cout((h/m-h%m)0); }最小表示法它是干什么的它怎么做的暴力枚举循环同构串的第一个位置然后暴力用字符串挨个比较的方法比较。时间复杂度获得 30 分。正解先将给定字符串我们先把复制粘贴一份在后面这样得到的新字符串​ 中任意长度为的字串都与循环同构。然后用双指针维护两个指针分别表示当前两种答案的开始位置然后枚举字串的长度 k当它们前个字符均相等即此时如果​那么说明以开头的答案不优直接否则。注意如果那么因为要保证我们是对不同的方案比较。当​ 且前个字符均相同时我们认为以开头的答案不优直接但是此时对于任意下标满足都不会是答案。因为一定存在对应的下标 比以为下标的答案更优。归根结底就是因为。根据这个原理我们可以更快速的查找答案。正确性时间复杂度无需证明。题目找不到因为只有模板题...如果你有的话你可以在讨论区提出我会万分感谢。后记这次主要讲的是较简单字符串专题我给出的那几道题建议全部独立完成如果你还有其他好题欢迎在讨论区提出。下次我会将几个自动机讲一下。对了你们来猜一下我是几年级答案会使你惊讶假设你看了那篇文章的话。您的肯定是我坚持的动力。