模板：manacher算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了模板：manacher算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1412字，纯文字阅读大概需要3分钟。

内容图文

https://www.luogu.org/problemnew/show/P3805

回文串长度的奇偶性造成了对称轴的位置可能在某字符上，也可能在两个字符之间的空隙处

那么manacher对此的优化是在每两个字符中间插入另一个字符，如'#'。

用一个辅助数组r表示每个点能够扩展出的回文长度

我们先设置一个辅助变量maxright，表示已经触及到的最右边的字符

另外还要设置一个辅助变量mid，表示包含maxright的回文串的对称轴所在的位置

当i在maxright左边且在mid右边时：

设i关于mid的对称点为j，显然r[i]一定不会小于r[j]。（对称）

我们没必要保存j，j可以通过计算得出，为：(mid<<1)?i

那么我们就设置r[i]=r[j]然后继续尝试扩展，这样就可以较快地求出r[i]，然后更新maxright和mid

当i在maxright右边时，我们无法得知关于r[i]的信息，只好从1开始遍历，然后更新maxright和mid

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 char t[11000010], a[11000010];
 6 int n, m, ans=0;
 7 int r[23000000];
 8 int main() {
 9     scanf("%s", t);
10     m=strlen(t);
11     a[0]=a[1]='#';
12     for(int i=1; i<=m; i++){
13         a[(i<<1)]=t[i-1];
14         a[(i<<1)+1]='#';
15     }
16     n=(m<<1)+2;
17     int mid=1, maxright=1;
18     r[1]=1;
19     for(int i=2; i<n; i++){
20         if(i<maxright) r[i]=min(r[(mid<<1)-i], r[mid]+mid-i); 
21         else  r[i]=1;
22         while(a[i-r[i]]==a[i+r[i]]) r[i]++;
23         if(i+r[i]>maxright){
24             maxright=i+r[i];
25             mid=i;
26         }
27         if(r[i]>ans)    ans=r[i];
28     }
29     printf("%d\n", ans-1);
30     return 0;
31 }

 

内容总结

以上是互联网集市为您收集整理的模板：manacher算法全部内容，希望文章能够帮你解决模板：manacher算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---