再谈最长回文子串——马拉车算法

之前说过一个算法，也是和字符串有关的——字符串的匹配算法。我们介绍了暴力匹配的BF算法，还有比较难以理解的KMP算法，最后还介绍了一种简单搞笑的Sunday算法。这里我们谈论的也是字符串问题，也就是前面所讲的最长回文子串问题，本来说是不再介绍这种适用性不强的算法的，但是这个马拉车算法和KMP算法是类似的，也是一种奇葩的算法，这里就稍微了解一下吧。

基本介绍

之前解决这个问题我们使用的是动态规划算法，时间复杂度是O(n²), 空间复杂度也是O(n²)。毫无疑问这个算法还是有一点儿低效的。之前字符串的暴力匹配的算法时间复杂度是O(nm)，使用KMP算法可以优化到O(n+m)，直接是优化了一整个等级。KMP算法思路是利用已经匹配失败之后的信息来帮助下一次匹配。马拉车算法也是如此，利用回文串匹配失败的信息来加速回文串的判断。