有没有谁能给我用最通俗的语言讲出马拉车算法的原理·，我感觉我要死了。

无法理解马拉车算法

大佬，是这样的，我现在正在做leedcode第五题，我现在对这个算法的理解是这样的：
求最大回文子串的方式有3种，1.暴力
2.动态规划
3.马拉车算法
前两个原理我已经搞懂，第三个我想不明白，
首先对于字符串的预处理：先对原来的字符串队首加入1个“#”字符，在根据原来需要求的原来的字符串按照一个字一个#号的方式传播。这样处理的目的是消除需要将原来字符串进行奇数个和偶数个分类。数学原理是无论是偶数还是奇数，在乘以2倍之后，再加1的情况下必然是奇数。

然后有个回文半径的概念，我理解就是回文串一半的长度。
然后再将处理后的字符串分情况讨论：
这里的概念就是确定一个左边界和右边界（这个我不知道是怎么确定的）
在左边界和右边界之间有一个中心点   左边界和右边界关于中心点对称
然后就是考虑回文串在左右边界里的情况，挨着边界的情况，超出边界这三种情况（这里很迷） 就是这里迷的的要死。

XFZYTY 发表于 2023-9-13 22:37
以下是对你的理解的一些进一步的解释：

1. 预处理：将原始字符串进行预处理，目的是为了解决奇数和偶数长 ...

别用gpt回复了，我真的感觉怪怪的