最长回文子串 最长回文子串英語Longest palindromic substring是计算机科学中的問題在一个字符串中查找一个最长的连续的回文的子串例如banana最长回文子串是anana最长回文子串并不一定是唯一的比如在abracadabra中没有超过个字符的回文子串但是有两个回文字串长度都是ada和aca在一些应用中我们求出全部的极大回文子串不被其他回文串包含的回文子串 Glenn Manacher 于年发现了一种线性时间算法可以在列出给定字符串中从任意位置开始的所有回文子串并且Apostolico Breslauer  Galil 发现同样的算法也可以在任意位置查找全部极大回文子串并且时间复杂度是线性的因此他们提供了一种时间复杂度为线性的最长回文子串解法另外Jeuring  Gusfield 发现了基于后缀树的算法也存在已知的高效并行算法 最长回文子串算法不应当与最长回文子序列算法混淆