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.

题目描述很简单，就是寻找一个字符串的最大回文。

1.暴力搜索

　穷举所有的可能，算法复杂度是O(n^3);

2.dp求解

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

3.对称

这里考虑到每个回文单词都是对称的，所以这里可以使用对称的思想进行解答。分别遍历以每个字母为中心的回文字符的最大长度，算法复杂度为O(n ^ 2);空间复杂度是

O(1);

 1 class Solution {
 2 public:
 3     string expand(string&s, int l, int h)
 4     {
 5         while((l >= 0) && (h < s.size()) && (s[l] == s[h]))
 6         {
 7             l--; h++;
 8         }
 9         
10         return s.substr(l+1, h-1-l);
11     }
12     
13     string longestPalindrome(string s) {
14         string res = s.substr(0,1);
15         
16         for(int i = 0; i < s.size(); i++)
17         {
18             string p;
19             p = expand(s, i, i);
20             
21             if(p.size() > res.size())
22                 res = p;
23             p = expand(s, i, i+1);
24             
25             if(p.size() > res.size())
26                 res = p;
27         }
28         
29         return res;
30     }
31 };

4。Manacher’s Algorithm

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

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