Manacher

它是干什么的

他是用来匹配回文串的，顾名思义就是用的时间复杂度匹配出最长回文串。

它怎么做的

暴力

首先我们知道暴力的写法，就是用的时间复杂度从每个节点暴力向外扩张，Manacher 解决的就是避免重复。

正解

核心思想是利用回文的对称性，避免重复计算。
可以处理奇回文和偶回文，通过插入分隔符统一处理。

1. 在字符串每两个字符之间及两端插入特殊字符（如 #），将奇偶回文统一为奇回文。

统一为奇回文为的是方便计算因为偶回文不太好统计。
2. 维护当前最右回文的中心和右边界。
3. 对于位置，若，则利用对称位置的信息初始化。
4. 暴力扩展求出的最长回文半径。
5. 更新和。

正确性

设当前最右回文为以为中心，右边界为的回文。
对于位置，设为关于的对称点。
如果：
以为中心的回文完全包含在以为中心的回文中。
由对称性，以为中心的回文长度与以为中心相同。
故。

如果：
以为中心的回文超出以为中心的回文范围。
由对称性，范围内的回文是确定的。
但r 右侧的字符未知，需要暴力扩展。
故，需要继续扩展。
初始化恰好覆盖了这两种情况。

由于扩张时只会扩张次，所以时间复杂度是。

code：

void manacher(){ n=strlen(s+1); int m=0; t[++m]='$'; for(int i=1;i<=n;i++) t[++m]=s[i],t[++m]='$';\\插入特殊字符 int M=0,R=0; for(int i=1;i<=m;i++){ if(i>R) p[i]=1; else p[i]=min(p[2*M-i],R-i+1);\\初始化 while(i-p[i]>0&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]]) ++p[i];\\暴力扩张统计答案 if(i+p[i]-1>R) M=i,R=i+p[i]-1;\\更新数值 } int ans=0; for(int i=1;i<=m;i++) ans=max(ans,p[i]);\\统计最大回文串 printf("%d",ans-1); }

题目

P1659 [国家集训队] 拉拉队排练

P4555 [国家集训队] 最长双回文串

P1659

由题意可知，显然每一个和谐群体就是一个长度为奇数的回文串。

用 Manacher 可以求每个位置的回文半径。

因为我们只要求奇数个的回文串，那么显然我们不需要在字符串里添加一些无关字符。

那么我们用Manacher求出以当前位置为中心的最长回文子串长度。

所以我们就会在求的同时搞出最长的。

然后根据对称性可知也有长为的回文子串，接着我们只需要统计一下就可以了。

注意我们只要奇数个，去掉偶数个。

因为数据范围过大，所以我们要快速幂使得不会爆掉。

code：

int main(){ scanf("%d%d%s",&n,&k,s+1),len=n,manacher(); for(int i=n;i;i--) { if(i%2==0) continue; sum+=cnt[i]; if(k>=sum) ans=(ans*quickpow(i,sum))%P,k-=sum;\\如果你很聪明你会把quickpow的值开_____，否则你只有 15 pts。 else{ ans=(ans*quickpow(i,k))%P,k-=sum; break; } } if(k>0) ans=-1; cout<<ans; }

P4555

就直接维护一个表示从出发往前的回文串最大长度，维护一个表示从出发往后的回文串最大长度，统计答案时直接把每个位置上的答案取最大值即可。

code：

void manacher(){ int m=0,M=0,R=0; n=strlen(s+1),t[++m]='$',t[0]='@'; for(int i=1;i<=n;i++) t[++m]=s[i],t[++m]='$'; for(int i=1;i<=m;i++){ if(i<R) p[i]=min(p[2*M-i],R-i+1); else p[i]=1; while(t[i-p[i]]==t[i+p[i]]) ++p[i]; if(i+p[i]-1>R) M=i,R=i+p[i]-1; l[i+p[i]-1]=max(l[i+p[i]-1],p[i]-1); r[i-p[i]+1]=max(r[i-p[i]+1],p[i]-1); } for(int i=3;i<=m;i+=2) r[i]=max(r[i],r[i-2]-2); for(int i=m;i>=3;i-=2) l[i]=max(l[i],l[i+2]-2); int ans=0; for(int i=3;i<=m;i+=2) if(r[i]&&l[i]) ans=max(ans,l[i]+r[i]); cout<<ans; }

如果你 WA on #12，#13，可以看看这个帖子。

KMP

我已经发过一遍博文了，详见这里。

exKMP(Z函数)

它是干什么的

能在的时间内处理出文本串的所有后缀和模式串的最长公共前缀。

其中和分别表示和的长度。

它怎么做的

暴力

你就要用的时间复杂度依次枚举。

正解

我们首先称最长公共前缀的前面部分为前半段，后面部分为后半段。

以abcabc为例，当时，abc=abc，前半段为第 1,2,3 个字符组成的abc，后半段为第 4,5,6 个字符组成的abc。

我们记录下为使得后端右端点最右的。

最长公共前缀是有对称性的。如上例abcabc，1 对应 4，2 对应 5，3 对应 6。假设 d 的最右端点大于等于，我们找到此时的对应点，此时：

• 若的后半段右端点已经超过前半段的右端点，此时我们无法利用全部部分，只能利用这一段部分的相等性。此时令。
• 若后半段右端点未超过前半段的右端点，则可以直接令。

然后我们暴力扩展至无法计算结束。所以本算法其实只有三步：

1. 根据当前得到一部分长度。
2. 暴力扩展，得到​。
3. 更新。

正确性

每次暴力扩展必会引起最右端点的右移，没有引起右移则只会操作 1 次，因此时间复杂度。

模板题code:

void Z(){ int l=0,r=0; z[1]=m; for(int i=2;i<=m;i++){ if(i<=r&&z[i-l+1]<r-i+1) z[i]=z[i-l+1]; else{ z[i]=max(0ll,r-i+1); while(i+z[i]<=m&&b[z[i]+1]==b[i+z[i]]) z[i]++; } if(i+z[i]-1>r) l=i,r=i+z[i]-1; } } void work(){ int l=0,r=0; for(int i=1;i<=n;i++){ if(i<=r&&z[i-l+1]<r-i+1) p[i]=z[i-l+1]; else{ p[i]=max(0ll,r-i+1); while(i+p[i]<=n&&p[i]<m&&b[p[i]+1]==a[i+p[i]])//如果你是 7 pts 那么有可能是这打错了 p[i]++; } if(i+p[i]-1>r) l=i,r=i+p[i]-1; } } signed main(){ cin>>(a+1)>>(b+1),n=strlen(a+1),m=strlen(b+1),Z(),work(); for(int i=1;i<=m;i++) ans^=1ll*i*(z[i]+1); cout<<ans<<endl,ans=0; for(int i=1;i<=n;i++) ans^=1ll*i*(p[i]+1); cout<<ans;//十年OI一场空，不开_____见祖宗 }

题目

P2375

CF526D

P2375

我们用 Z 函数求出每个后缀与原串的，然后很轻松的利用差分统计答案即可。Z 函数可以在O(N)的时间内求出每个后缀与原串的，他类似于马拉车算法，也是递推地求解。

假设我们要求第个后缀的，我们已经求出来前个，维护匹配一个最右端的指针，记此时的后缀为，原串为。是那么我们可以发现i如果位于的左面的话，我们可以利用之前的结果更新当前的，然后再暴力扩展，随时更新一下指针，和 Manacher 其实是一个道理。

void solve(){ memset(lcp,0,sizeof lcp),memset(t,0,sizeof t),pos=r=0,ans=1,cin>>(s+1),len=strlen(s+1); for(int i=2;i<=len;++i){ if(pos==0){ int p=1; while(s[p+lcp[i]]==s[i+lcp[i]]) ++lcp[i]; if(lcp[i]) r=i+lcp[i]-1,pos=i; continue; } if(i>r){ int p=1; while(s[p+lcp[i]]==s[i+lcp[i]]) ++lcp[i]; if(lcp[i]) r=i+lcp[i]-1,pos=i; continue; } int npos=i-pos+1; lcp[i]=min(lcp[npos],r-i+1); while(s[lcp[i]+1]==s[i+lcp[i]]) ++lcp[i]; if(i+lcp[i]-1>r) r=i+lcp[i]-1,pos=i; } for(int i=2;i<=len;++i) if(lcp[i]) t[i]++,t[min(2*(i-1),min(len,i+lcp[i]-1))+1]--; for(int i=1;i<=len;++i) t[i]+=t[i-1]; for(int i=1;i<=len;++i) ans=ans*(t[i]+1)%mod; cout<<ans<<endl; }

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 的数量除以大，还是模大，就可以判断了。

code：

while(i<n){ if(j==-1||s[i+1]==s[j+1]) i++,j++,nxt[i]=j; else j=nxt[j]; } for(int i=1;i<=n;i++){ p=i-nxt[i],h=i/p; if(i%p) cout<<((h/m-h%m)>0); else cout<<((h/m-h%m)>=0); }

最小表示法

它是干什么的

它怎么做的

暴力

枚举循环同构串的第一个位置，然后暴力用字符串挨个比较的方法比较。

时间复杂度获得 30 分。

正解

先将给定字符串，我们先把复制粘贴一份在后面，这样得到的新字符串​ 中任意长度为的字串都与循环同构。

然后用双指针维护，两个指针分别表示当前两种答案的开始位置，然后枚举字串的长度 k，当它们前个字符均相等，即

此时，如果​，那么说明以开头的答案不优，直接，否则。

注意：如果那么，因为要保证我们是对不同的方案比较。

当​ 且前个字符均相同时，我们认为以开头的答案不优，直接，但是此时对于任意下标满足都不会是答案。因为一定存在对应的下标， 比以为下标的答案更优。归根结底，就是因为。根据这个原理，我们可以更快速的查找答案。

正确性

时间复杂度：，无需证明。

题目

找不到，因为只有模板题...

如果你有的话你可以在讨论区提出，我会万分感谢。

后记

这次主要讲的是较简单字符串专题，我给出的那几道题建议全部独立完成，如果你还有其他好题，欢迎在讨论区提出。

下次我会将几个自动机讲一下。

对了，你们来猜一下我是几年级，答案会使你惊讶，假设你看了那篇文章的话。

您的肯定是我坚持的动力。