陈思琪-冯冠宇-最长回文字串的线性方法

ManacherAlgorithm——一个解决最长回文子串的线性方法 计42冯冠宇陈思琪引出概念作业中提到了子串以及回文的概念现在引入最长回文子串的概念:在一个字符串S(母串)中存在一个子串A满足 子串A回文，即A[i]=A[len-i-1] (len=strlen(A),0<=i<len)称A为回文子串最长的满足条件的A称为最长回文子串引出概念举个例子:Confuciussay：Madam,I’mAdam去掉大写以及符号空格S=“confuciussaymadamimadam”存在回文子串“ada”“madam”“amima”“ss”等最长回文子串为“madamimadam”一个问题给定一个母串S，求最长回文子串三个子问题：当S的长度len(S)为: (1)0<=len(S)<=500 (2)0<=len(S)<=10000 (3)0<=len(S)<=20000000第一问简单方法O(n^3)两重循环O(n^2)确定首尾得到一个子串O(n)对子串进行回文判定第二问对于每一个字符，向两边查找，发现不同则break;

可以得到以其为中心的最长子串对于所有得到的子串取最长的即可有两种情况：(1)“madam”“ma”与“am”相对于“d”对称

(2)“maddam”“mad”与”dam”直接对称则对于每个字符S[i]，以S[i]为中心做一次，再以S[i]和S[i+1]为中心做一次一个小技巧考虑第二种情况在中心S[i]和S[i+1]间加入一个虚拟字符S[k]

（与其他字符均不相同即可，一般设为“#”）

情况可以转化为第一种，以S[k]为中心进行查找得到的结果为正确的结果加1(即加上了S[k])一个小技巧那么对于母串S每两个字符之间加上虚拟字符（包括第一个字符前以及最后一个字符后）假设原得到的回文子串为A[1]~A[k]加入虚拟字符后，得到的回文子串为#A[1]#A[2]#...#A[k-1]#A[k]#长度为2k+1（含有k+1个“#”）第三问事实上，不同字符所求出的最长子串之间存在一定联系而前面的方法没有利用到这种联系接下来讨论一个优美的算法——ManacherManacher根据之前提到的技巧，以下我们只讨论以一个字符为中心所得到回文串设定一个数组P：P[i]表示以A[i]为中心得到回文串向右延伸的长度（即(回文串长度+1)/2)如果能得到P数组，最长回文子串显然可以很快的求出问题转换为求P数组Manacher算法是从前往后进行的，所以当我们需要计算P[i]时，P[k](0<=k<i)都已求出记录mx为之前回文串向右延伸到的最右端的位置（max{k+P[k]-1}0<=k<i）记录id为得到mx的kManacherj为i点关于id的对称点，j=2*id-I当i>mx时显然i==mx+1此时可以当做第二种情况判断第一种情况id的回文串完全覆盖j的回文串（id-p[id]+1<j-p[j]+1)此时由于i，j关于id对称，显然p[i]=p[j]Manacher第二种情况当id的回文串无法完全覆盖j的回文串时（包含刚好覆盖的情况）（id-p[id]+1>=j-p[j]+1)对i的回文串显然被id的回文串覆盖的部分已经确定回文只需对超出部分进行判断（下图…部分）Manacher得到新的结果可以更新id与mx值id更新为imx更新为i+p[i]-1