最长回文子串（Longest Palindromic substring）

什么叫回文串

就是正读和反读都是一样的字符串，比如aba,abba,cdc像这样的字符串都是回文字符串

 暴力破解法来查找最长的回文子串

这个图解的意思就是我们要拿到每一个右边的数，然后与左边的数一一匹配

下面看一下java的实现代码

package com.pxx;
 
/**
 * Created by Administrator on 2023/9/11.
 */
public class Test2 {
 
    public static String longestPalindrome(String s) {
        if (s == null) {
            return null;
        }
 
        //从最右边才是最长的，越往里面走，越短
        for (int len = s.length(); len >= 1; len--) {
            //这里i + len是保证你每一个回文串的长度来整体字符串长度之内
            for (int start = 0; start + len <= s.length(); start++) {
                if (isPalindrome(s,start,start + len - 1)) {
                    return s.substring(start,start + len);
                }
            }
        }
        //没有结果就返回空串
        return "";
    }
 
    //直接判断是否是回文数
    private static boolean isPalindrome(String s,int left,int right) {
        while (left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        //如果是回文数的情况下，肯定会造成left >= right的，某种情况来说，left == right程序就已经截止了
        return left >= right;//为真就是回文串，为假就不是回文串
    }
 
    public static void main(String[] args) {
        String res = longestPalindrome("abcdzdcab");
        System.out.println(res);
    }
}

下面是c语言代码实现

#include 
#include 
#include 
 
// 判断是否是回文字符串
bool isPalindrome(const char* s, int left, int right) {
    while (left < right && s[left] == s[right]) {
        left++;
        right--;
    }
    return left >= right;
}
 
// 查找最长回文子串
const char* longestPalindrome(const char* s) {
    if (s == NULL) {
        return NULL;
    }
    for(int len = strlen(s); len >= 1; len--) {
        for(int start = 0; start + len <= strlen(s); start++) {
            if(isPalindrome(s,start,start + len - 1)) {
                char* result = (char*)malloc(sizeof(char) * (start + len));
                strncpy(result, s + start, start + len - 2);
                result[start + len] = '\0';
                return result;
            }
        }
    } 
 
    return "";
}
 
int main() {
    const char* input = "abcdzdcab";
    const char* result = longestPalindrome(input);
 
    printf("Input: %s\n", input);
    printf("Longest palindrome: %s\n", result);
 
    free((void*)result); // 释放动态分配的内存
 
    return 0;
}

上面这个算法的时间复杂度是O(n^3) 

 

基于中心点的枚举法Enumeration来实现查找最长子串

实现原理

 

上面是大体实现，具体要分奇数回文串来看或者偶数回文串来看 

 奇数部分代码实现原理分析

 偶数部分代码实现原理分析

 下面是java代码实现

public class Enumeration {
 
	//主体函数
	//拿到字符串里面的最长回文字符串
	public static String longestPolindrom(String s) {
		//安全性检查
		if(s == null) {
			return null;
		}
		//定义一个我们需要返回的字符串
		String longest = "";
		//遍历整个字符串然后检查
		for(int i = 0; i < s.length(); i++) {
			//这里是奇数部分的查找
			String oddPolindrome = getPolindromeFrom(s,i,i);//之前分析过，奇数其实就是固定一点，左右散发，这里是i
			//判定一下是否把得到的回文串给替换不
			if (longest.length() < oddPolindrome.length()) {//小于返回的就替换，因为我们要找最长的
				longest = oddPolindrome;//直接把这个字符串给替换
			}
			//这里是偶数串的查找
			String evenPolindrome = getPolindromeFrom(s,i,i+1);//偶数串就不能固定一个点
			if (longest.length() < evenPolindrome.length()) {
				longest = evenPolindrome;
			}
		}
		
		//上面循环完之后返回
		return longest;
		
	}
 
	//得到回文字符串
	public static String getPolindromeFrom(String s, int left, int right) {
		//双指针，相向而行的一个双指针
		while (left >= 0 && right < s.length()) {
			if (s.charAt(left) != s.charAt(right)) {
				break;//先break掉
			}
			left--;
			right++;
			
		}
		//最后直接截断
		//这个截断是包头不包尾
		//left这个位置已经是不相等的位置了
		return s.substring(left + 1,right);
	}	
 
	public static void main(String[] args) {
		String res = longestPolindrom("abcdzdcab");
		System.out.println(res);
	}
}

运行结果：

 下面是c++代码实现

#include 
#include 
#include 
 
 
using namespace std;
 
//写一个函数返回回文字符串的长度
int expand_around_center(const string& s,int left,int right) 
{
	int len = s.length();
	while (left >= 0 && right < len && s[left] == s[right]) {
		left--;//往左边扩展
		right++;//往右边扩展
	}
	//一旦上面不满足了，就返回这个长度
	return right - left -1; 
}
 
//主函数：查找最长的回文子串
string longest_palindrome(const string& s) 
{
	int start = 0, end = 0;//初始化最长回文子串的起始位置与结束位置
 
	int len = s.length();
	for (int i = 0; i < len; i++) {
		//开始轮替，这里分为奇数轮替与偶数的轮替
		int len1 = expand_around_center(s,i,i);
		int len2 = expand_around_center(s,i,i + 1);
 
		//上面都会返回文子串的长度，也有可能返回0，我们就取其中最大的就行了
		int max_len = max(len1,len2);//依赖头文件
 
		//如果当前返回的长度 > 之前记录的长度
		//需要更新起始位置与结束位置
		//这段代码直接背下来
		if (max_len > end - start) {
			start = i - (max_len - 1) / 2;
			end = i + max_len / 2;
		}
	}
 
	//上面整体循环完了之后，start与end都是边界，然后用substr截取
	return s.substr(start,end - start + 1);//为什么加1，因为end -start就会少一个数 2 4 =》 4 - 2 + 1
}
 
int main() 
{
	string input = "abcdzdcab";
	string result = longest_palindrome(input);
	printf("input : %s\n",input.c_str());
	//这是c++的方法，可以理解为把string->char*，然后让printf进行打印
	printf("Longest palindrom: %s\n",result.c_str());
	return 0;
}

运行结果：

下面用图解的方式对c++的部分进行分析

 解析1：right  - left - 1

解析2：

 

有几个小的知识点我得说一下：

第一个：关于-1/2=0,本来应该是-0.5,但是1与2都是整型嘛，然后后面就截断了 0不占符号位，如果还是-4/2 = -2,这个时候就得有符号位

第二个：printf()不能打印char*的c语言类型的字符串，所以字符串可以调用c_str()函数变成包含了c语言指针的字符串

那如果我们用c语言处理呢，就把上面代码修改一下就可以了下面看代码

#include 
#include 
#include 
 
// 辅助函数：查找以left和right为中心的最长回文子串
int expandAroundCenter(char *s, int left, int right) {
    int len = strlen(s);
    while (left >= 0 && right < len && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;//这里返回回文串的长度
}
 
// 主函数：查找最长回文子串
char *longestPalindrome(char *s) {
    int start = 0; // 最长回文子串的起始位置
    int end = 0;   // 最长回文子串的结束位置
 
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        // 以每个字符为中心，分奇数和偶数长度回文子串两种情况进行扩展
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
 
        // 取两种情况中的较长者
        int maxLen = len1 > len2 ? len1 : len2;
 
        // 如果当前回文子串的长度大于之前记录的最长回文子串长度
        // 则更新起始和结束位置
        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = i + maxLen / 2;
        }
    }
 
    // 根据起始和结束位置截取最长回文子串
    char *result = (char*)malloc(sizeof(char) * (end - start + 2));
    strncpy(result, s + start, end - start + 1);
    result[end - start + 1] = '\0';
 
    return result;
}
 
int main() {
    char input[] = "babad";
    char *result = longestPalindrome(input);
 
    printf("Input: %s\n", input);
    printf("Longest Palindrome: %s\n", result);
 
    free(result); // 释放分配的内存
 
    return 0;
}

下面是对一部分核心代码的讲解

 这个算法的时间复杂度是O(n^2)

先说到这