Manacher算法笔记中，如何处理长尾词的匹配问题？

本文共计766个文字，预计阅读时间需要4分钟。

Part 1: 算法概述该算法由Glenn K. Manacher于1975年提出，是一种在O(N)时间复杂度下求解字符串所有回文子串的算法，也是寻找最大回文子串最高效的方法。算法的难点主要在于理解。

part 1 算法简述

该算法由 Glenn K. Manacher 在 1975 年提出，是一种可以在O(N)时间复杂度下求字符串所有回文子串的算法，也是求最大回文子串最高效的算法。该算法的难度主要在于理解。

part 2 算法详解

求最大回文字串，首先要注意奇回文串与偶回文串的区别，如果不进行处理统一，就会使代码变得很复杂。

那么怎么来统一呢？

可以在每两个字符之间加上字符串中不曾出现的字符（包括头和尾），这样就可以使得字符串长度变为奇数，原因如下：

\(设原字符串长度为k,则经过操作后变为2k+1,必定为奇数.\)

例如：

解决了字符串统一的问题，接下来需要思考怎么优化求最大回文字串的过程。（\(O(n^2)\)的暴力算法在此不做介绍）

按照以往的经验，减少求回文的次数是关键，我们需要尽量使用已经拥有的数据。

此处分成两种情况：

• 1. 当前枚举的回文中心点在最大回文串内。

  这种情况，是最简单的情况，我们可以运用回文的对称性，使用大回文串的另一边的对称点的数据。