首页 > 代码库 > Longest Palindromic Substring问题
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.
样例：
S="acbbcc"
return "cbbc"
首先考虑的果然还是枚举的办法，没什么技术含量，O(n^2)的时间复杂度，直接贴代码了：
#include <string.h>char* longestPalindrome(char* s) { int i,j,k1,k2,i_tmp,len,max[2]={0,0}; len=strlen(s); for(i=0;i<len-1;i++){ j=i-1; i_tmp=i+1; while(s[i_tmp]==s[i_tmp-1]){ i_tmp++; if(i_tmp>len-1) break; } while(s[j]==s[i_tmp]&&i_tmp<=len-1&&j>=0){ j--; i_tmp++; } i_tmp--,j++; if(i_tmp-j>max[1]-max[0]){ max[0]=j; max[1]=i_tmp; } } char *answer=malloc((max[1]-max[0]+2)*sizeof(char)); for(k1=0,k2=max[0];k2<=max[1];k2++) answer[k1++]=s[k2]; answer[k1]=‘\0‘; return answer;}
击败52%的C提交，看起来提升空间应该蛮大的。因为官方带Editorial Solution，所以我就偷个懒，直接看看还有哪些解法了。
第一个解法也是O(n^2)的算法。颠倒字符串S得到字符串S1，寻找S和S1的最长公共子串，如果公共子串的下标值相同，它就是我们要找的最长回文子串，如果不是，我们跳过它接着寻找。思路不难理解，但寻找两个字符串的最长公共子串也挺麻烦的，这里我就不用这种算法了。
之后看到一个巧妙的O(n)算法，其实就是我上面写的算法的改进。我写的算法对于每一个元素都朝元素两边扩张来计算以它为中心的回文字串的大小，也就是说从元素本身，从一开始扩张。而这个O(n)算法的思想是利用回文字符串的对称性减少一些不必要的计算，说白了也就是说不从元素本身开始扩张。而是利用回文字符串的对称性，利用之前已经计算过的元素的回文字串大小来避免从一开始扩张的情况。具体可以看看下面这篇博客：
https://www.felix021.com/blog/read.php?2040
下面贴一下我根据这个思路改进的代码（顺便修改了一些原来没写好的地方）
char* longestPalindrome(char* s) { int i,j,i_tmp,max[2]={0,0},p[1100],mid_l=0,mid_r=0,maxP=0; for(i=0;i<1100;i++) p[i]=0; for(i=0;s[i+1]!=‘\0‘;i++){ j=i-1; while(s[i]==s[i+1]) i++; i_tmp=i+1; if(i<mid_r+maxP&&i+p[mid_l-(i-mid_r)]<=mid_r+maxP){ j-=p[mid_l-(i-mid_r)]; i_tmp+=p[mid_l-(i-mid_r)]; } while(s[j]==s[i_tmp]&&i_tmp!=‘\0‘&&j>=0){ j--; i_tmp++; } i_tmp--,j++; p[i]=i_tmp-i; if(i_tmp-j>max[1]-max[0]){ max[0]=j; max[1]=i_tmp; mid_r=i; for(i_tmp=i;i_tmp==i_tmp-1;i_tmp--) ; mid_l=i_tmp; maxP=mid_l-j; } } char *answer=malloc((max[1]-max[0]+2)*sizeof(char)); for(i=0,j=max[0];j<=max[1];j++) answer[i++]=s[j]; answer[i]=‘\0‘; return answer;}
之所以是p[1100]而不是p[1000]是因为我用p[1000]的时候竟然说我runtime error了，不知道leetcode搞什么鬼，于是加了100。
注意我的算法是把连续的元素当作一个整体处理的，所以我分了mid_l和mid_r。
运行时间达到了惊人的0ms..(-_-)，击败了99%的C提交，看来这一波很强势，好的，那今天就到这收工。
Longest Palindromic Substring问题