转载

Longest Palindromic Substring

题目：

Given a string S , find the longest palindromic substring in S . You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路：

这题其实就是问 Manacher 算法——O(n)回文子串算法。回文串开始比较纠结的是奇偶串判别方法不同，用一个比较巧妙的方法将其统一成奇串：先在每两个相邻字符中间插入一个分隔符，这个分隔符要在原串中没有出现过，一般可以用‘#’分隔。这样回文串保证了都是奇数。用一个 数组 p 记录以每个字符为中心的最长回文串长度 ，即：p[id] 记录的是以字符 s[id] 为中心的最长回文串长度，举例：

原串   :   a   b   c   d   c   b   a   f 
拷贝串 : # a # b # c # d # c # b # a # f #
数组 p : 1 2 1 2 1 2 1 8 1 2 1 2 1 2 1 2 1

容易证明， p[id] - 1 就是回文子串在原串中的长度 ，如上例中，最长子串为 abcdcba ，长度为7，p[8] - 1 = 7。现在问题变成如何算出数组 p 。用变量 i 逐个扫描字符串，变量 MaxId 记录扫描串时所到达的最右边的下标，用 id 记录扫描到最右边串时当前子串的中心，结合以下代码理解下变量意思：

if (MaxId < i + p[i]){     MaxId = i + p[i];     id = i; }

要在O(n)时间内找到最长回文串，也就是说当扫描子串时最长扫到了 MaxId 的位置，那么在 i 遍历到 MaxId 之前我们都不需要重新扫描，而是能直接通过某个性质得到当前 p[i] ，先给出核心代码：

if (MaxId > i)    p[i] = min(MaxId - i, p[id + id  - i]); else              p[i] = 1;

id + id - i 是 i 关于 id 的对称点，设为 j ， p[j] 是以 j 为中心的最长回文串长度，也就是以 j 为中心扫描过的长度，MaxId 是当前扫描到的最右边，结合下图理解：我们在算 p[i] 时，由于回文串的特点可以知道 p[i] 就等于 p[j] ，但是若 i + p[i] 的长度超过了 MaxId ，这之后的字符是还未扫描过的，即在计算 p[i] 时，它所能确定的最长不能超过 MaxId - i ，也不能超过 i 的对称点 j 所扫描的长度 p[j] ，所以取两者间的小值。见图：

Longest Palindromic Substring

p[i] = p[j];

Longest Palindromic Substring

p[i] = MaxId - i;

代码：

 1 #define min(a,b) (a) > (b)? (b): (a)  2 char* longestPalindrome(char* s) {  3     char auxStr[2001];  4     int i, p[2001] = {0}, MaxId = 0, id = 0, leng, j, start = 0;  5       6     auxStr[0] = '^';  7     for (i = 0; s[i] != '/0'; ++i){  8         auxStr[i+1+i+1] = s[i];  9         auxStr[i+1+i] = '#'; 10     } 11     auxStr[i+1+i] = '#'; 12     auxStr[i+1+i+1] = '/0'; 13     for (i = 1; auxStr[i] != '/0'; ++i){ 14         if (MaxId > i) 15             p[i] = min(MaxId - i, p[id + id  - i]); 16         else 17             p[i] = 1; 18         while (auxStr[i + p[i]] == auxStr[i - p[i]]) 19             ++p[i]; 20         if (MaxId < i + p[i]){ 21             MaxId = i + p[i]; 22             id = i; 23         } 24         if (p[start] < p[i]) 25             start = i; 26     } 27     i = (start - p[start])/2; 28     leng = p[start] - 1; 29     for (j = 0; j < leng; ++i){ 30         auxStr[j++] = s[i]; 31     } 32     auxStr[j] = '/0'; 33     return auxStr; 34 }