题目:
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.
最长回文字串,原型应该是ACM一道题目,不过这个已经简化很多了,只要把每一个位置作为回文的中心,往两边匹配找到回文长度,返回这些长度中最大的即可。有一个要注意的地方是奇数与偶数的情况。代码:
1 string longestPalindrome(string s) { 2 // IMPORTANT: Please reset any member data you declared, as 3 // the same Solution instance will be reused for each test case. 4 int start,len,maxLen=0; 5 len=s.length(); 6 for(int i=0;i<len;i++){ 7 for(int j=0;i-j>=0&&i+j<len;j++){ 8 if(s[i-j]!=s[i+j]) break; 9 if(j*2+1>maxLen){ 10 maxLen=j*2+1; 11 start=i-j; 12 } 13 } 14 for(int j=0;i-j>=0&&i+j+1<len;j++){ 15 if(s[i-j]!=s[i+j+1]) break; 16 if(j*2+2>maxLen){ 17 maxLen=j*2+2; 18 start=i-j; 19 } 20 } 21 } 22 return s.substr(start,maxLen); 23 }