Manacher/马拉车算法(Java版本)

Manacher算法：也叫 “马拉车”算法。

Manacher算法与最长回文子串查找

什么是回文串：

所谓回文串，指的是一个字符串在正向与反向阅读时内容完全一致，例如abba、noon等。对于某一特定字符串而言，其最长回文子串即为所有子串中长度最大且满足回文特性的那一部分。

计算回文串的多种方法

计算字符串中最长回文子串的最基础方法是遍历该字符串的所有可能子串，并逐一验证其是否为回文结构，该方法的时间复杂度为O(n³)，显然难以满足实际需求。稍作改进的策略是通过确定回文子串的中心点进行枚举，此时需要考虑两种情形：一种是回文长度为奇数的情形，另一种则是回文长度为偶数的情形。通过对中心点的枚举并进行回文判断，可将时间复杂度降低至O(n²)，然而当字符串长度较大时，该方法仍存在效率不足的问题。Manacher算法则能够在O(n)的时间复杂度内求解最长回文子串，从而实现理论上的最优性能。

1.Manacher算法原理与实现：

Manacher算法与回文串处理

（1）Len数组简介与性质

Man