给定一个字符串,求它的最长回文子串的长度。
/**
* @param s
* @param n
* @return
*/
bool IsPalindrome(const char *s, int n){
if(s== NULL||n<1){
return false;
}
for (int i = 0; i < n/2; ++i) {
if(s[i]!=s[n-i-1]){
return false;
}
}
return true;
}/**
* 穷举法遍历所有长度 O(n^3)
* @param s
* @param n
* @return
*/
int LongestPalindrome(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
int longest=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n-i;j++){
if(IsPalindrome(s+j,i)){
longest=longest<i?i:longest;
}
}
}
return longest;
}
/**
* 找中心点向外扩散 O(n^2)
* @param s
* @param n
* @return
*/
int LongestPalindrome2(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
int longest=0;//长度
//i是中心点下标
for (int i = 0; i <n ; ++i) {
//j是长度
//奇数串
for (int j = 0;(i-j)>=0&&(i+j)<n; ++j) {
if(s[i-j]!=s[i+j]){
break;
}
int c=j*2+1;
longest=longest<c?c:longest;
}
for (int j = 0;(i-j)>=0&&(i+j+1)<n; ++j) {
if(s[i-j]!=s[i+j+1]){
break;
}
int c=j*2+2;
longest=longest<c?c:longest;
}
}
return longest;
}
/**
* Manacher算法 O(n)
* @param s
* @param n
* @return
*/
int LongestPalindrome3(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
char str[n*2+4];
int j=0;
str[j++]='$';
str[j++]='#';
for (int i = 0; i < n; ++i) {
//使回文串长度变成偶数
str[j++]=*(s+i);
str[j++]='#';
}
str[j]='\0';
int p[j-1];//保存以下标为中心点的最长回文串长度
memset(p,0, sizeof(p));
int mx=0;//回文串最右边界
int idx=0;//回文串中心点
int longest=0;//最长子串
for(int i=1;i<j-1;i++){
p[i]=mx>i?min(mx-i,p[2*idx-i]):1;//2*idx-i 与i关于idx对称,如果p[2*idx-i]比mx-i长则说明p[i]>=p[2*idx-i] 短的话 p[i]=p[2*idx-i]
while(str[i-p[i]]==str[i+p[i]]){
p[i]++; //继续求p[i]的最长回文串
}
longest=p[i]>longest?p[i]:longest;
if(p[i]+i>mx){
mx=p[i]+i;
idx=i;
}
}
return longest-1;
}