回文(Palindromic)就是正序、逆序读取完全一样的字符串。中文中像“画上荷花和尚画”、“书临汉帖翰林书”等这样的对联就是读音相同的回文。当然，回文字符串要求更严格，对应位置的字符要完全相同，如奇数位的“aba”、偶数位的“abba”。若如此，本段文字中符合定义的中文回文恐怕只有“中文中”这三个字。
假使给出一段字符串，从中找出最长的一段回文，这就要用到最长回文子串算法。注意任何字符串都会有最大回文子串，因为单个字符本身就可以看做是一个回文串。
解决这类问题的算法有很多，核心是要弄清各个算法对应的复杂度，适当选用，个人觉得是重中之重。关于这些算法，我适当参考了一下Leecode，对这个算法的阐述很好，特地注明，其他能在网上找到的相关中文资料都是翻译它的，大多没有注明来源，个人觉得这种行为比较无耻。
一般最容易的想法是将所给字符串进行逆序排列，然后找出利用之前介绍的longest common substring算法找出最大公共子串，即为最大回文子串。这里需要需要注意的是找到的最大公共子串的字符在两个字符串的位置应该处于对称位置，即在一个字符串的位置是经过逆序排列后所处字符串的位置。如果不是不符合这种条件找到的最大公共子串不是最大回文串，如“ababba”，可自行验证。所以说这种算法要进行多余步骤的验证，一般不用。
接下来介绍的算法也很符合人类思维，应该算是一种笨方法。就是用之前介绍的string searching算法找出所有长度大于2的子串，之后再按长度由大到小的顺序一一验证这些子串是否是回文串，算法可参考之前给出的代码写出，不难。找出所有字串的时间复杂度是O(n2)，而验证各个子串是否问回文串需要O(n)，所以这个算法的时间复杂度为O(n3)。
这个算法的复杂度太高，有没有更好的算法呢？这类问题，一般都会想到用DP的方法解决。
DP的原理也比较简单，掌握它的状态转换方程即可，这里不进行论述，可以参考Leecode。代码如下：
string longestPalindromeDP(string s) {int n = s.length();int longestBegin = 0;int maxLen = 1;bool table[1000][1000] = {false};for (int i = 0; i < n; i++) {table[i][i] = true;}for (int i = 0; i < n-1; i++) {if (s[i] == s[i+1]) {table[i][i+1] = true;longestBegin = i;maxLen = 2;}}for (int len = 3; len <= n; len++) {for (int i = 0; i < n-len+1; i++) {int j = i+len-1;if (s[i] == s[j] && table[i+1][j-1]) {table[i][j] = true;longestBegin = i;maxLen = len;}}}return s.substr(longestBegin, maxLen);}
这个算法的时间和空间复杂度都为O(n2).也可以对这个代码进行优化，将其空间复杂度将为O(n)，代码如下：
string expandAroundCenter(string s, int c1, int c2) {int l = c1, r = c2;int n = s.length();while (l >= 0 && r <= n-1 && s[l] == s[r]) {l--;r++;}return s.substr(l+1, r-l-1);}string longestPalindromeSimple(string s) {int n = s.length();if (n == 0) return "";string longest = s.substr(0, 1);for (int i = 0; i < n-1; i++) {string p1 = expandAroundCenter(s, i, i);if (p1.length() > longest.length())longest = p1;string p2 = expandAroundCenter(s, i, i+1);if (p2.length() > longest.length())longest = p2;}return longest;}
最后，要介绍的是算法复杂度为O(n)的算法，也是最重要的算法——Manacher’s Algorithm。这种算法的原理比较难理解，想要掌握这种算法的话一定弄明白，我写的Java代码如下：
public static String Manacher(String s){//written by YimengString T=preProcess(s);int n=T.length();int[] cache=new int[n];int C=0,R=0;int maxLen = 0;int centerIndex = 0;for(int i=1;i<n-1;i++){int mirror = 2*C-i;if(i<R){if(cache[mirror]<(R-i)) cache[i]=cache[mirror];else cache[i]=R-i;}while (T.charAt(i + 1 + cache[i])== T.charAt(i - 1 - cache[i]))cache[i]++;if (i+cache[i]>R){C=i;R=i+cache[i];}}for (int i = 1; i < n-1; i++) {if (cache[i] > maxLen){maxLen = cache[i];centerIndex = i;}}return s.substring((centerIndex-1-maxLen)/2,(centerIndex-1+maxLen)/2);}private static String preProcess(String s) {StringBuilder str=new StringBuilder();str.append('^');for(int i=0;i<s.length();i++)str.append("#" + s.charAt(i));str.append("#$");return str.toString();}
最后总结一下，最大回文串算法平时的应用不是特别多，属于中级偏上的算法，一般面试中比较常遇到，DP算法一定要熟练掌握，Manacher最好也熟练掌握，属于额外加分题。
文章评论