manacher算法（回文字符串）

柔情只为你懂 2022-05-24 02:17 199阅读 0赞

定义数组p\[i\]表示以i为中心的(包含i这个字符)回文串半径长

将字符串s从前扫到后for(int i=0;i<strlen(s);++i)来计算p\[i\],则最大的p\[i\]就是最长回文串长度,则问题是如何去求p\[i\]?

由于s是从前扫到后的,所以需要计算p\[i\]时一定已经计算好了p\[1\]....p\[i-1\]

假设现在扫描到了i+k这个位置,现在需要计算p\[i+k\]

定义maxlen是i+k位置前所有回文串中能延伸到的最右端的位置,即maxlen=p\[i\]+i;//p\[i\]+i表示最大的

分两种情况:

1.i+k这个位置不在前面的任何回文串中,即i+k>maxlen,则初始化p\[i+k\]=1;//本身是回文串

然后p\[i+k\]左右延伸,即while(s\[i+k+p\[i+k\]\] == s\[i+k-p\[i+k\]\])++p\[i+k\]

2.i+k这个位置被前面以位置i为中心的回文串包含,即maxlen>i+k

这样的话p\[i+k\]就不是从1开始

由于回文串的性质,可知i+k这个位置关于i与i-k对称,

所以p\[i+k\]分为以下3种情况得出

//黑色是i的回文串范围,蓝色是i-k的回文串范围,

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

转自：[点击打开链接][Link 1]

[SouthEast]: /images/20220524/d23eb621f37349769114e67193d1ab15.png
[SouthEast 1]: /images/20220524/3c7da35e362a426286fb4c282784ac50.png
[SouthEast 2]: /images/20220524/755bc57adbec42eaabb777dd512c114a.png
[SouthEast 3]: /images/20220524/883c96081b89440db3f9f3610866f6bc.png
[Link 1]: https://blog.csdn.net/xingyeyongheng/article/details/9310555

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关最长回文(manacher算法,最大回文子串)

Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba,

刺骨的言语ヽ痛彻心扉/ 2024年02月17日 19:27/ 0 赞/ 42 阅读

相关 hihoCoder#1032 : 最长回文子串(manacher算法)

参考http://blog.csdn.net/xingyeyongheng/article/details/9310555 include<iostream>

╰+攻爆jí腚メ/ 2022年08月21日 00:05/ 0 赞/ 215 阅读

相关 O(n)的回文子串Manacher算法

O(n)的回文子串Manacher算法算法代码实现如下：样例输入： abab bbbb abba 样例输出： 3 4

待我称王封你为后i/ 2022年07月26日 11:15/ 0 赞/ 160 阅读

相关最长回文串——manacher算法java实现

最长回文串是一个很好玩的话题，给出一个无序的不定长的字符序列，如何知道里面的最长回文串呢？ manacher算法的思想是 1 把偶数、奇数长的字符序列变成奇数长度 2 创

我会带着你远行/ 2022年06月10日 03:23/ 0 赞/ 258 阅读

相关【模板——ing】O(n)回文子串（Manacher）算法

1.模板适应问题：（1）：输入串st，求出串st中最长回文子串 2.模板代码： include <cstdio> include <cstring>

系统管理员/ 2022年06月07日 02:55/ 0 赞/ 150 阅读

相关 Manacher算法(求最长回文字符串长度)

![这里写图片描述][70] // public class StringProblem{ //Manacher算法预处理

深碍√TFBOYSˉ_/ 2022年05月26日 04:00/ 0 赞/ 258 阅读

相关 manacher算法（回文字符串）

定义数组p\[i\]表示以i为中心的(包含i这个字符)回文串半径长将字符串s从前扫到后for(int i=0;i<strlen(s);++i)来计算p\[i\],则最大的p

柔情只为你懂/ 2022年05月24日 02:17/ 0 赞/ 200 阅读

相关【3068 HDU】最长回文串（Manacher算法）

题目：[点击打开题目链接][Link 1] 思路：这题要用到回文串匹配的知识点。我们之前遇到这种题传统思想就是分奇数和偶数情况进行暴力，从前往后遍历每一个字符，然后以该字符为

忘是亡心i/ 2022年05月10日 13:26/ 0 赞/ 247 阅读

相关回文子串问题之Manacher算法

写在前面回文子串问题。题目简述 > 时间限制:1000ms > 单点时限:1000ms > 内存限制:256MB > 描述 > 小Hi和小Ho

短命女/ 2022年05月09日 23:22/ 0 赞/ 206 阅读

相关 (manacher 1.1)hdu 3068回文(使用manacher判断回文简单题)

最长回文 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

小鱼儿/ 2022年03月01日 06:06/ 0 赞/ 187 阅读