马拉车算法
2020-10-21 15:22:28 2 举报求最长回文子串算法详解
作者其他创作
大纲/内容
算法
a b a a c a a b a
a b c a c b a b c b
马拉车算法则巧妙的利用到之前已经求出的最长回文串
对称轴
但是当我们的字符 串快到边界时如右图右边的b，参照对称轴，得左边b的范围，此时右边b的回文串的长度已经到达了最右边（之前求的最长回文串最右边），由于右边是未知的所以我们要继续中心扩展求以b为对称轴最长回文串，如果我们求得回文串长度大于之前的，我们就可以更新最长回文串
在边界内无需中心扩展
正常情况下我们求一个字符串的回文串这样（暴力求解）
此时我们在遍历下一个元素c，我们是否有必要计用中心扩展的方式（以c为中心向两边比较）计算c的回文串，其实没有必要，我们以之前求最长子串的中心为对称轴找到对称点第三个字符c，我们可以知道只要第三个字符c为中心的回文串的范围在这个我们之前求得的最长回文串中，我们此时的字符c与第三个字符c的回文串是一样的。看下面例子。
如上字符串，我们要先遍历每一个字符，然后以遍历的每一个字符为中心向两边扩展，求得最长的回文串。这里我们要遍历每一个字符串并且每一个都要做中心到两边的扩展。所以时间复杂度为O(N平方)
回文串的概念是一个字符串正着读和反着读是一样的如\"aba\"正反都是\"aba\"。马拉车算法是用之前已经求过的最长回文子串来避免后面不必要的重复计算。
如左所示当我们遍历到第4个字符a时，我们求得他的回文串为\"abcacba\"
超出右边界需要中心扩展
a b c a c b a b c b
右边界
所以我们需要维护一个数组，Len[i] = r 第 i 个字符为中心最长回文串的半径。当然我们也要保存当前最长回文串的对称轴以及右边界（超出右边界以及在右边界上的回文串我们要继续中心扩展）
马拉车算法解决最长回文子串
所以我们的马拉车算法巧妙的运用到了之前已经求出的子串的，来避免了重复计算提高了效率
我们可以知道对称轴左右两边，是完全镜面对称的，即我们随便取一点该点与对称点的回文串是相同的。如我们图中取的b点。所以当我们求到最长回文子串对称轴之后的字符时我们可以参照前面的字符的回文串。
0 条评论
下一页
