a linear-time algorithm for longest palindromic substring

http://www.felix021.com/blog/read.php?2040

用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]），比如S和P的对应关系：

S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1 (ps. 可以看出，P[i]-1正好是原字符串中回文串的总长度）

 

//输入，并处理得到字符串s/* id -- 回文中心位置 mx -- 回文右邊界*/ int p[1000], mx = 0, id = 0; memset(p, 0, sizeof(p)); for (i = 1; s[i] != '\0'; i++) { p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;while (s[i + p[i]] == s[i - p[i]]) p[i]++;if (i + p[i] > mx) { mx = i + p[i]; id = i; } } //找出p[i]中最大的

 

這裡有個來龍去脈：

http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

 

for more: Another algorithm

http://www.akalin.cx/longest-palindrome-linear-time

转载于:https://www.cnblogs.com/prajna/archive/2013/03/02/2941125.html