现在位置: 首页 / 学习 / leetcode / 正文

LeetCode第五题： 最长回文子串

  • admin
  • 学习
  • 2023-09-12
  • 48热度
  • 0评论

题目来源：LeetCode第五题

1.题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

2.解题思路

解法一：暴力法（过不了）

  • 描述：直接枚举所有可能的字串，对于每一个字串都判断是不是回文
  • 时间复杂度：O(n^3)。用到了两层循环来枚举出所有字串，在用一个循环来判断是不是回文，所以时间复杂度为O(n^3)。
  • 空间复杂度：O(1)。只使用了几个变量，而没有使用与输入大小成比例的额外空间。
  • 参考代码：

java版：

class Solution {
    public String longestPalindrome(String s) {
        // 判断字符串为空，直接返回
        if (s == null || s.length() < 1)
            return "";
        // 用来记录最长回文字符串的起始和结束位置
        int start = 0, end = 0;

        // 外层循环确定字串起始位置
        for (int i = 0; i < s.length(); i++) {
            // 内层循环确定字串的结束位置，结束位置需要在起始位置的后面，所以从i开始
            for (int j = i; j < s.length(); j++) {
                // 用自己定义的判断回文方法来判断从i到j的字串是不是回文
                // 如果是并且新的回文长度>原来记录的最长长度，则将新的起始和结束位置赋值
                if (isPalindroms(s, i, j) && (j - i) > (end - start)) {
                    start = i;
                    end = j;
                }
            }
        }
        // 返回字串，注意这个substring的后一个参数是不包含的，需要取到end+1
        return s.substring(start, end + 1);
    }

    // 自定义的回文判断方法
    private boolean isPalindroms(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }

}

C++版：

class Solution
{
public:
	string longestPalindrome(string s) {
		int n = s.size();
		if (n <= 1)
			return s;
		//用start记录开始索引，maxlen记录长度
		int start = 0, maxlen = 0;
		// 外层循环确定字串起始位置
		for (int i = 0; i < n; i++)
		{
			// 内层循环确定字串的结束位置，结束位置需要在起始位置的后面，所以从i开始
			for (int j = i; j < n; j++)
			{
				//如果字串为回文并且新的回文长度大于之前记录的最长长度，对起始位置和长度进行更新
				if (isPalindrome(s, i, j) && (j - i + 1) > maxlen)
				{
					start = i;
					maxlen = j - i + 1;
				}
			}
		}
		//返回最长回文字串
		return s.substr(start, maxlen);
	}
private:
	//自定义的判断回文函数
	bool isPalindrome(const string& s, int start, int end)
	{
		while (start < end)
		{
			if (s[start++] != s[end--])
			{
				return false;
			}
		}
		return true;
	}
};

C版：

bool isPalindrome(char* s, int start, int end) {
	while (start < end) {
		if (s[start++] != s[end--]) {
			return false;
		}
	}
	return true;
}

char* longestPalindrome(char* s) {
	int len = strlen(s);
	int start = 0, maxLen = 0;

	for (int i = 0; i < len; i++) {
		for (int j = i; j < len; j++) {
			if (isPalindrome(s, i, j) && (j - i + 1) > maxLen) {
				start = i;
				maxLen = j - i + 1;
			}
		}
	}

	char* result = (char*)malloc((maxLen + 1) * sizeof(char));
	for (int i = 0; i < maxLen; i++) {
		result[i] = s[start + i];
	}
	result[maxLen] = '\0';

	return result;
}

解法二：中心扩展法

  • 描述：考虑到回文可以是奇数长度或者偶数长度，我们可以定义一个字符为一个中心，以及每两个相邻字符之间的间隙为一个中心，因此，对于一个长度为n的字符串，我们有2n-1个中心，从每个中心开始向外扩展，检查字符是否相同，相同就继续扩展，不同就停止
  • 时间复杂度：O(n^2)。对于每个中心，扩展的复杂度是 O(n)，因为在最坏的情况下，你可能要向外扩展到字符串的两端。由于我们有 2n - 1 个中心，所以总的时间复杂度是 O(n*(2n-1))=O(n^2)。
  • 空间复杂度：O(1)。除了原始的输入字符串和一些变量来跟踪最长的回文子串外，我们没有使用其他的额外空间。因此，空间复杂度是 O(1)。
  • 参考代码：

java版：

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1)
            return "";
        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度的回文串中心是一个字符
            int len1 = expandFromCenter(s, i, i);
            // 偶数长度的回文串中心是两个字符
            int len2 = expandFromCenter(s, i, i + 1);

            // 取两个长度的最大值
            int len = Math.max(len1, len2);

            // 判断当前的回文长度是否比之前存的更长，更长的话就更新。
            if (len > end - start) {
                // 奇数长度的回文，例如aba，中心是b，len是3，中心索引是i
                // 那么start索引是i-1，end索引是i+1
                // 偶数长度的回文，例如abba 中心算在bb之间，len是4，假设中心在第一个b
                // 那么start索引是i-1，end索引是i+2
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    // 自定义中心扩展方法，s是字符串，left和right是当前的中心
    private int expandFromCenter(String s, int left, int right) {
        // 确保向两边扩展的时候依然满足回文的条件，left >= 0 是不会超出字符串左边界
        // right < s.length()向右扩展的时候不会超出字符串右边界
        // 确保从当前中心向左和向右扩展的字符都是相同的
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 当循环结束的时候，left和right会分别指向回文字符串的前一个位置和后一个位置
        // 此时的回文字符串长度为right-left-1
        return right - left - 1;
    }
}

C++版：

class Solution {
public:
    	string longestPalindrome(string s)
	{
		if (s.empty())
		{
			return "";
		}
		// 用于记录最长回文子串的起始和结束位置
		int start = 0, end = 0;

		for (int i = 0; i < s.size(); i++)
		{
			// 奇数长度的回文串中心是一个字符
			int len1 = expandFromCenter(s, i, i);
			// 偶数长度的回文串中心是两个字符
			int len2 = expandFromCenter(s, i, i + 1);
			// 取两个长度的最大值
			int len = max(len1, len2);
			// 判断当前的回文长度是否比之前存的更长，更长的话就更新。
			if (len > end - start)
			{
				// 奇数长度的回文，例如aba，中心是b，len是3，中心索引是i
				// 那么start索引是i-1，end索引是i+1
				// 偶数长度的回文，例如abba 中心算在bb之间，len是4，假设中心在第一个b
				// 那么start索引是i-1，end索引是i+2
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		// 使用substr函数返回找到的最长回文子串
		return  s.substr(start, end - start + 1);
	}

private:
	// 自定义中心扩展方法，s是字符串，left和right是当前的中心
	int expandFromCenter(const string& s, int left, int right)
	{
		// 确保向两边扩展的时候依然满足回文的条件，left >= 0 是不会超出字符串左边界
		// right < s.length()向右扩展的时候不会超出字符串右边界
		// 确保从当前中心向左和向右扩展的字符都是相同的
		while (left >= 0 && right < s.length() && s[left] == s[right])
		{
			left--;
			right++;
		}
		// 当循环结束的时候，left和right会分别指向回文字符串的前一个位置和后一个位置
		// 此时的回文字符串长度为right-left-1
		return right - left - 1;
	}
};

C版：

int expandFromCenter(const 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) {
    if (s == NULL) return NULL;

    int len = strlen(s);
    if (len == 0) return "";

    int start = 0, end = 0;

    for (int i = 0; i < len; i++) {
        int len1 = expandFromCenter(s, i, i);
        int len2 = expandFromCenter(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)); // 额外的1用于'\0'结束字符
    if (!result) return NULL; // 内存分配失败

    int j = 0;
    for (int i = start; i <= end; i++) {
        result[j++] = s[i];
    }
    result[j] = '\0';

    return result;
}

解法三：动态规划

  • 描述：动态规划就是用空间换时间，避免重复计算。我们定义一个二维数组dp[i][j]来表示字串s[i......j]是否为回文串，如果i=j，只有一个字符，那么dp[i][j]为真，j=i+1 即字串长度为2，如果两个字符相同，则dp[i][j]为真，如果j>i+1,即字串长度大于2，那么dp[i][j]取决于s[i]是否等于s[j]以及字串s[i+1.......j-1]是否为回文，即取决于dp[i+1][j-1]。
  • 时间复杂度：O(n^2)。两层循环。
  • 空间复杂度：O(n^2)。用二维数组来存储每个字串的情况。
  • 参考代码：

java版：

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        // 长度小于2的话直接返回
        if (len < 2)
            return s;

        // 定义二维数组来存放起始地址和结束地址中间的元素是不是回文的
        // dp[i][j] = true代表s[i....j]这个字串是回文的
        // 要知道s[i....j]是不是回文的，可以看s[i+1....j-1]是不是回文的
        // 也就是看dp[i+1][j-1]是不是true，如果是并且s[i]=s[j]的话，说明dp[i][j]=true
        boolean[][] dp = new boolean[len][len];

        int start = 0;
        // 这里设置为1，因为substring后面的数字不包含在内
        // 如果为ab的话可以返回a而不是空
        int maxlen = 1;

        // 初始化对角线上的元素，都设置为true
        // 因为下标11之间的元素只有一个，一个元素肯定是回文的
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        // 这里j放外层循环，是为了保证在判断dp[i][j]的时候已经判断过dp[i+1][j-1]
        // 就是为了先判断较小的字串,例如aba,想知道aba是不是回文需要知道b是不是回文
        // 例如abcba,想知道abcba是不是回文，需要先知道bcb是不是回文
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                // 如果首尾两端的元素相等
                if (s.charAt(i) == s.charAt(j)) {
                    // 这个是为了处理字符串长度为2或者3的情况
                    // 如果为2或者3并且两端的元素相等，说明肯定是回文的
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        // 长度不为2或者3的话，就取决于字串是不是回文的，这个值在之前已经计算过了
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    // 首尾两端不一样直接false
                    dp[i][j] = false;
                }
                // 如果是回文的，并且长度也大于之前记录过的最长，替换结果
                if (dp[i][j] && j - i + 1 > maxlen) {
                    start = i;
                    maxlen = j - i + 1;
                }
            }
        }
        // 返回结果
        return s.substring(start, start + maxlen);
    }
}

C++版：

class Solution
{
public:

	string longestPalindrome(string s)
	{
		// 长度小于2的话直接返回
		int len = s.size();
		if (len < 2)
		{
			return s;
		}
		// 定义二维数组来存放起始地址和结束地址中间的元素是不是回文的
		// dp[i][j] = true代表s[i....j]这个字串是回文的
		// 要知道s[i....j]是不是回文的，可以看s[i+1....j-1]是不是回文的
		// 也就是看dp[i+1][j-1]是不是true，如果是并且s[i]=s[j]的话，说明dp[i][j]=true
		vector<vector<bool>> dp(len, vector<bool>(len, false));

		int start = 0, maxlen = 1;

		// 初始化对角线上的元素，都设置为true
		// 因为下标11之间的元素只有一个，一个元素肯定是回文的
		for (int i = 0; i < len; i++)
		{
			dp[i][i] = true;
		}

		// 这里j放外层循环，是为了保证在判断dp[i][j]的时候已经判断过dp[i+1][j-1]
		// 就是为了先判断较小的字串,例如aba,想知道aba是不是回文需要知道b是不是回文
		// 例如abcba,想知道abcba是不是回文，需要先知道bcb是不是回文
		for (int j = 1; j < len; j++)
		{
			for (int i = 0; i < j; i++)
			{
				// 如果首尾两端的元素相等
				if (s[i] == s[j])
				{
					// 这个是为了处理字符串长度为2或者3的情况
					// 如果为2或者3并且两端的元素相等，说明肯定是回文的
					if (j - i < 3)
					{
						dp[i][j] = true;
					}
					else
					{
						// 长度不为2或者3的话，就取决于字串是不是回文的，这个值在之前已经计算过了
						dp[i][j] = dp[i + 1][j - 1];
					}
				}
				else
				{
					// 首尾两端不一样直接false
					dp[i][j] = false;
				}
				// 如果是回文的，并且长度也大于之前记录过的最长，替换结果
				if (dp[i][j] && j - i + 1 > maxlen)
				{
					start = i;
					maxlen = j - i + 1;
				}
			}
		}
		return s.substr(start, maxlen);
	}
};

C版：

char* longestPalindrome(char* s) {
	int len = strlen(s);

	// 当字符串长度小于2时，返回整个字符串作为回文串
	if (len < 2) {
		char* res = (char*)malloc(2 * sizeof(char));
		res[0] = s[0];
		res[1] = '\0';
		return res;
	}

	int maxLength = 1; // 最长回文子串的初始长度为1
	char* start = s;  // 指向最长回文子串起始位置的指针

	// 初始化动态规划二维数组
	bool** dp = (bool**)malloc(len * sizeof(bool*));
	for (int i = 0; i < len; i++) {
		dp[i] = (bool*)malloc(len * sizeof(bool));
		memset(dp[i], 0, len * sizeof(bool));
		dp[i][i] = true;  // 单个字符始终是回文串
	}

	// 动态规划计算所有可能的子串是否为回文串
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < i; j++) {
			// 如果两个字符相同，并且它们之间的子串也是回文串，那么当前子串是回文串
			dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));

			// 如果找到更长的回文子串，更新maxLength和start
			if (dp[j][i] && maxLength < i - j + 1) {
				maxLength = i - j + 1;
				start = s + j;
			}
		}
	}

	// 从原字符串中提取最长回文子串
	char* result = (char*)malloc((maxLength + 1) * sizeof(char));
	for (int i = 0; i < maxLength; i++) {
		result[i] = start[i];
	}
	result[maxLength] = '\0';

	// 清除动态规划数组
	for (int i = 0; i < len; i++) {
		free(dp[i]);
	}
	free(dp);

	return result;
}

解法四：动态规划（优化空间）

  • 描述：我们用一个一维数组dp[j]来存i到j的字串是不是回文，这个巧妙的地方在于不需要二维数组来记录所有的字串，因为我们只是需要当前字串和上一些循环中的字串的状态。我们两个循环都是从后往前进行的，那样就自然的知道了i+1的状态了，比如在这一轮循环中，想知道i到j的字串是不是回文的，只需要知道两端想不想等，还有i+1和j-1的字串是不是回文就行，而这一轮的i+1和j-1就是上一轮的i和j。
  • 时间复杂度：O(n^2)。依然是两个嵌套循环，时间复杂度不变
  • 空间复杂度：O(n)。只用了一个一维数组
  • 参考代码：

java版：

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();

        // 初始时，我们假设最长回文子串为空
        String res = "";

        // 创建一个布尔数组，用于存储子字符串是否为回文的信息
        // dp[j]表示从i到j的字串是否回文
        boolean[] dp = new boolean[len];

        // 外层从字符的末尾开始遍历，将从当前i到最后一位之间回文最长的记录下来与之前的进行比较
        for (int i = len - 1; i >= 0; i--) {
            // 内层循环也是从末尾开始，一直到i，这样就完成了到i的所有子串的搜索
            for (int j = len - 1; j >= i; j--) {
                // 这里我举个例子abaaba 刚开始i和j都是5，这时候肯定相等，满足判断条件，所以说dp[5]=true
                // 然后i等于4，j等于5，b不等于a，不满足条件dp[5]变成了false，然后j--变成4，都为4的话肯定满足
                // dp[4]=true，然后i等于3，j等于5，此时a=a，并且满足字串长度小于等于3,dp[4]也为true
                // 所以dp[5]又等于true，更新结果，然后j--，不满足条件，dp[4]=false，j--，j又等于i了，所以dp[3]=true
                // i--,i=2,j=5,满足了s[i]=s[j]，但是dp[j-1]也就是dp[4]是flse，这是上一轮循环i+1的时候我们得到的i+1到j-1的结果
                // dp[5]=false,j--,不满足,dp[4]=false,j--,此时j=3，满足了条件，所以dp[3]=true，然后j--，dp[2]=true
                // i--，i=1，j=5，不满足,dp[5]=false,j--,j=4,满足了条件，并且上次循环，已经保存了当前的i+1和当前的j-1是回文的结果
                // 也就是dp[3],所以dp[4]=true,更新条件，j--，dp[3]=false，j--，dp[2]=false，j--，dp[1]=true。
                // i--，i=0,j=5,此时满足条件，因为我们同样保存了i+1到j-1的回文结果，所以dp[5]=true,更新结果
                // j--,不满足，dp[4]=false,dp[3]=false,dp[2]=true，dp[1]=true,i--,循环结束，输出我们保存的最长回文字串

                // s.charAt(i) == s.charAt(j)判断两端是否相等，j - i < 3 判断长度是否小于等于3
                // dp[j - 1]是判断i+1到j-1的字串是不是回文，为什么可以看到i+1呢，是因为上一轮循环判断的，因为j总是从最右边开始
                // 现在的i+1就是上一轮的i，这一轮的j-1也就是上一轮的j，所以都已经判断过了，这个dp是一直在更新的，只需要知道上一轮的情况就行了
                // 对于在早一点的情况完全没有必要知道，因为我们按照dp的状态转移方程根本不需要知道
                dp[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[j - 1]);

                if (dp[j] && j - i + 1 > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
}

C++版：

class Solution {
public:
 string longestPalindrome(string s)
{
	int len = s.size();
	if (len <= 1)
		return s;
	// 用于保存最长回文子串的起始位置和长度
	int start = 0, maxlen = 0;
	// 创建一个布尔数组，用于存储子字符串是否为回文的信息
	// dp[j]表示从i到j的字串是否回文
	vector<bool> dp(len, false);

	// 外层从字符的末尾开始遍历，将从当前i到最后一位之间回文最长的记录下来与之前的进行比较
	for (int i = len - 1; i >= 0; i--)
	{
		// 内层循环也是从末尾开始，一直到i，这样就完成了到i的所有子串的搜索
		for (int j = len - 1; j >= i; j--)
		{
			// 这里我举个例子abaaba 刚开始i和j都是5，这时候肯定相等，满足判断条件，所以说dp[5]=true
			// 然后i等于4，j等于5，b不等于a，不满足条件dp[5]变成了false，然后j--变成4，都为4的话肯定满足
			// dp[4]=true，然后i等于3，j等于5，此时a=a，并且满足字串长度小于等于3,dp[4]也为true
			// 所以dp[5]又等于true，更新结果，然后j--，不满足条件，dp[4]=false，j--，j又等于i了，所以dp[3]=true
			// i--,i=2,j=5,满足了s[i]=s[j]，但是dp[j-1]也就是dp[4]是flse，这是上一轮循环i+1的时候我们得到的i+1到j-1的结果
			// dp[5]=false,j--,不满足,dp[4]=false,j--,此时j=3，满足了条件，所以dp[3]=true，然后j--，dp[2]=true
			// i--，i=1，j=5，不满足,dp[5]=false,j--,j=4,满足了条件，并且上次循环，已经保存了当前的i+1和当前的j-1是回文的结果
			// 也就是dp[3],所以dp[4]=true,更新条件，j--，dp[3]=false，j--，dp[2]=false，j--，dp[1]=true。
			// i--，i=0,j=5,此时满足条件，因为我们同样保存了i+1到j-1的回文结果，所以dp[5]=true,更新结果
			// j--,不满足，dp[4]=false,dp[3]=false,dp[2]=true，dp[1]=true,i--,循环结束，输出我们保存的最长回文字串

			// s.charAt(i) == s.charAt(j)判断两端是否相等，j - i < 3 判断长度是否小于等于3
			// dp[j - 1]是判断i+1到j-1的字串是不是回文，为什么可以看到i+1呢，是因为上一轮循环判断的，因为j总是从最右边开始
			// 现在的i+1就是上一轮的i，这一轮的j-1也就是上一轮的j，所以都已经判断过了，这个dp是一直在更新的，只需要知道上一轮的情况就行了
			// 对于在早一点的情况完全没有必要知道，因为我们按照dp的状态转移方程根本不需要知道
			dp[j] = s[i] == s[j] && ((j - i) < 3 || dp[j - 1]);


			if (dp[j] && j - i + 1 > maxlen)
			{
				start = i;
				maxlen = j - i + 1;
			}
		}
	}
	return s.substr(start, maxlen);
}
};

C版：

char* longestPalindrome(char* s) {
	int n = strlen(s);
	if (n <= 1) return s;

	int start = 0, maxLength = 0; // 用于保存最长回文子串的起始位置和长度
	bool* P = (bool*)malloc(n * sizeof(bool));

	for (int i = n - 1; i >= 0; --i) {
		for (int j = n - 1; j >= i; --j) {
			// 状态转移方程
			P[j] = s[i] == s[j] && (j - i < 3 || P[j - 1]);

			// 如果当前子串是回文，并且它的长度大于之前的最长回文子串
			if (P[j] && j - i + 1 > maxLength) {
				maxLength = j - i + 1;
				start = i;
			}
		}
	}

	char* result = (char*)malloc((maxLength + 1) * sizeof(char));
	for (int i = 0; i < maxLength; i++) {
		result[i] = s[start + i];
	}
	result[maxLength] = '\0';

	free(P);
	return result;
}

解法五：马拉车算法

  • 描述：我们通过插入#方式来让字符串变成奇数，这样就不用讨论奇偶的问题，并且我们用一个数组 P 保存从中心扩展的最长回文子串的半径。使用两个指针 C 和 R。C 是当前已知的最长回文子串的中心，R 是该子串的右边界。对于当前考虑的中心 i，如果 i 在 R 的左侧，可以找到 i 关于 C 的对称点 i'。我们可以利用 P[i'] 来尝试预测 P[i]。具体有三种情况：如果 P[i'] 不超过 R-i，那么 P[i] 至少有 P[i'] 那么大。如果 P[i'] 超过 R-i，那么 P[i] 至少有 R-i 那么大。如果 P[i'] 正好在 R-i，那么 P[i] 的值不确定，需要从 R 开始扩展。如果扩展后的以 i 为中心的回文子串的右边界超过 R，则更新 C 和 R 的值。
  • 时间复杂度：O(n)。将原始字符串转换为加入特殊字符后的字符串，时间复杂度是O(n)。尽管存在一个外层循环来遍历字符串中的每一个字符，但由于内层循环的扩展是基于已知的回文串信息，并且每次扩展都会将右边界 R 向右移动，每个字符至多被访问两次（一次是作为中心，一次是作为已知回文串的一部分）。因此，构建 P 数组的操作也是O(n)。
  • 空间复杂度：O(n)。预处理后的字符串长度是 2n + 3（包括特殊字符），所以其空间复杂度是O(n)。P 数组用于存储每个字符为中心的回文串的长度，长度等于预处理后的字符串长度，所以其空间复杂度是O(n)。
  • 参考代码：

java版：

class Solution {
    public String longestPalindrome(String s) {
        // 如果字符串为空，直接返回空字符
        if (s == null || s.length() == 0) {
            return "";
        }

        // 预处理字符串
        String str = preprocess(s);
        int len = str.length();
        // 用一个数组存储以str[i]为中心的回文字串的半径，不含本身
        // 例如^#c#b#c#b#c#$ s[6]=c,以c为中心的回文字串是#c#b#c#b#c#
        // 半径是#b#c#(不含中心c)，所以p[6] = 5
        int[] p = new int[len];

        // C是中心的下标，R表示回文串的右边下标
        // 例如^#c#b#c#b#c#$ i=6时，C=6，R=11
        int C = 0, R = 0;

        // 从下标1开始，因为前面的^只是拿来当边界
        for (int i = 1; i < len - 1; i++) {
            // mirror是i以C为对称轴的对称点
            // 例如^#c#b#c#b#c#$
            // C=6，前面的b下标是4，当i加到后面的b时，i=8
            // 前面的b就是后面b的对称点，满足4=2*6-8
            int mirror = 2 * C - i;

            // 其实我们就是维护了一个最右回文串，让R尽量在靠右的位置
            // 这样，我们才可以利用对称特性来快速得到在回文串中的中心点右边点的回文半径
            // 这样，在进行中心扩展的时候就不需要一个一个做，可以从记录的回文半径外来扩展
            // 例如^#c#b#c#b#c#$，当i运行到c时，我们通过中心扩展获得了一个最右回文串
            // ..0 123456789101112
            // 即^|#c#b#c#b#c#|$，这时i=6，在i++，等于7，发现这个点在我们维护的回文串中，所以可以直接赋值
            // p[] 010105......... 找到对称点5，发现p[5]=0,所以p[7]=0,然后在进行扩展从i + (p[i] + 1)开始
            // ..0 123456789101112.......也就是比较c和b想不想等，不相等，而且新的R也就是i + p[i]没以前的R右，所以R不变
            // ..^|#c#b#c#b#c#|$........继续i++，到8，通过对称点4可以知道p[8]=1,所以在进行扩展的时候从i+2开始，也就是比较下标10和6
            // p[] 01010503..................发现相等，继续扩展，到不相等为止,扩展完后，p[8]=3 边界不变

            // 直接根据对称点赋值就一定是对的吗，不一定
            // 首先是对称过来的点的下标太大了，如果加上这个值就直接超过了R，我们根本就不知道R外面的情况，所以导致出错
            // 例如^#f#a#b#c#b#a#d#a#b#c#b#e#$ 运行到中间的d，我们可以维护范围内的点，但是继续运行到后面的c时
            // ...^#f#a|#b#c#b#a#d#a#b#c#b#|e#$ 我们根据对称发现前一个c的p=5,我们不可能在扩展时从i+6开始，因为已经超过R了
            // 对于这种情况，我们可以直接扩展到边界，因为我们可以保证到边界的字串是回文的，接着在从边界开始扩展就行

            // 如果i在当前的最右回文串中，可以利用对称加快得到当前点i的p值
            if (R > i) {
                // 防止对称过来的p值加上i超过R，超过的话就将半径设为到边界的长度
                // 因为在这个范围内，我们可以保证是回文的
                p[i] = Math.min(R - i, p[mirror]);
            }

            // R以外的区域进行中心扩展法扩展，可以利用对称过来的p值减少计算，直接算未知的点
            while (str.charAt(i + (p[i] + 1)) == str.charAt(i - (p[i] + 1))) {
                p[i]++;
            }
            // 如果当前中心加上半径超过了原来的最右边界，说明最右边界可以更新了，不管这个回文串大不大
            // 我们需要让边界能右移就移动，是为了让之后的i尽量小于R，这样可以多多利用对称的特性
            if (i + p[i] > R) {
                C = i;
                R = i + p[i];
            }
        }

        // 到这里，我们已经获得了一个存储当前点的回文半径的数组
        // 可以通过这个数组来得到最长回文字串
        int maxlen = 0;
        int centerIndex = 0;
        // 通过循环，找到最大回文半径长度，记录下来并记录该中心点
        for (int i = 1; i < len - 1; i++) {
            if (p[i] > maxlen) {
                maxlen = p[i];
                centerIndex = i;
            }
        }

        // 这是找到原字符串的下标
        // 例如^|#a#b#a#b#a#|a#$ 原字符串ababaa的最长回文串为ababa
        // 我们获得的中心点是6 最长半径是5 通过公式，得出start是0
        int start = (centerIndex - maxlen) / 2;
        // 返回结果
        return s.substring(start, start + maxlen);
    }

    // 自定义的预处理字符串方法，让字符串永远为奇数
    // 例如abba，处理后变成^#a#b#b#a#$,这样让我们不用在考虑奇偶判断
    // 左右两边多加一个不一样的字符是为了在中心扩展时，判断两端元素是否相等时一定不相等
    // 自动退出循环，这样就可以不用判断边界了
    private String preprocess(String s) {
        StringBuffer sb = new StringBuffer();
        sb.append("^");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#");
            sb.append(s.charAt(i));
        }
        sb.append("#$");
        return sb.toString();
    }
}

C++版：

class Solution {
public:
    	string longestPalindrome(const string& s)
	{
		// 预处理字符串
		string str = preProcess(s);
		int len = str.size();
		// 用一个数组存储以str[i]为中心的回文字串的半径，不含本身,初始化为0
	   // 例如^#c#b#c#b#c#$ s[6]=c,以c为中心的回文字串是#c#b#c#b#c#
	   // 半径是#b#c#(不含中心c)，所以p[6] = 5
		vector<int> p(len, 0);

		// C是中心的下标，R表示回文串的右边下标
		// 例如^#c#b#c#b#c#$ i=6时，C=6，R=11
		int C = 0, R = 0;

		// 从下标1开始，因为前面的^只是拿来当边界
		for (int i = 1; i < len - 1; i++)
		{
			// mirror是i以C为对称轴的对称点
			// 例如^#c#b#c#b#c#$
			// C=6，前面的b下标是4，当i加到后面的b时，i=8
			// 前面的b就是后面b的对称点，满足4=2*6-8
			int mirror = 2 * C - i;

			// 其实我们就是维护了一个最右回文串，让R尽量在靠右的位置
			// 这样，我们才可以利用对称特性来快速得到在回文串中的中心点右边点的回文半径
			// 这样，在进行中心扩展的时候就不需要一个一个做，可以从记录的回文半径外来扩展
			// 例如^#c#b#c#b#c#$，当i运行到c时，我们通过中心扩展获得了一个最右回文串
			// ..0 123456789101112
			// 即^|#c#b#c#b#c#|$，这时i=6，在i++，等于7，发现这个点在我们维护的回文串中，所以可以直接赋值
			// p[] 010105......... 找到对称点5，发现p[5]=0,所以p[7]=0,然后在进行扩展从i + (p[i] + 1)开始
			// ..0 123456789101112.......也就是比较c和b想不想等，不相等，而且新的R也就是i + p[i]没以前的R右，所以R不变
			// ..^|#c#b#c#b#c#|$........继续i++，到8，通过对称点4可以知道p[8]=1,所以在进行扩展的时候从i+2开始，也就是比较下标10和6
			// p[] 01010503..................发现相等，继续扩展，到不相等为止,扩展完后，p[8]=3 边界不变

			// 直接根据对称点赋值就一定是对的吗，不一定
			// 首先是对称过来的点的下标太大了，如果加上这个值就直接超过了R，我们根本就不知道R外面的情况，所以导致出错
			// 例如^#f#a#b#c#b#a#d#a#b#c#b#e#$ 运行到中间的d，我们可以维护范围内的点，但是继续运行到后面的c时
			// ...^#f#a|#b#c#b#a#d#a#b#c#b#|e#$ 我们根据对称发现前一个c的p=5,我们不可能在扩展时从i+6开始，因为已经超过R了
			// 对于这种情况，我们可以直接扩展到边界，因为我们可以保证到边界的字串是回文的，接着在从边界开始扩展就行

			// 如果i在当前的最右回文串中，可以利用对称加快得到当前点i的p值
			if (R > i)
				// 防止对称过来的p值加上i超过R，超过的话就将半径设为到边界的长度
				// 因为在这个范围内，我们可以保证是回文的
				p[i] = min(R - i, p[mirror]);

			// R以外的区域进行中心扩展法扩展，可以利用对称过来的p值减少计算，直接算未知的点
			while (str[i + (p[i] + 1)] == str[i - (p[i] + 1)]) 
				p[i]++;

			// 如果当前中心加上半径超过了原来的最右边界，说明最右边界可以更新了，不管这个回文串大不大
			// 我们需要让边界能右移就移动，是为了让之后的i尽量小于R，这样可以多多利用对称的特性
			if (i + p[i] > R)
			{
				C = i;
				R = i + p[i];
			}
		}

		// 到这里，我们已经获得了一个存储当前点的回文半径的数组
		// 可以通过这个数组来得到最长回文字串
		int maxLen = 0;
		int centerIndex = 0;
		// 通过循环，找到最大回文半径长度，记录下来并记录该中心点
		for (int i = 1; i < len - 1; i++)
		{
			if (p[i] > maxLen)
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}

		// 这是找到原字符串的下标
		// 例如^|#a#b#a#b#a#|a#$ 原字符串ababaa的最长回文串为ababa
		// 我们获得的中心点是6 最长半径是5 通过公式，得出start是0
		int start = (centerIndex - maxLen) / 2;
		return s.substr(start, maxLen);
	}
private:
	// 自定义的预处理字符串方法，让字符串永远为奇数
	// 例如abba，处理后变成^#a#b#b#a#$,这样让我们不用在考虑奇偶判断
	// 左右两边多加一个不一样的字符是为了在中心扩展时，判断两端元素是否相等时一定不相等
	// 自动退出循环，这样就可以不用判断边界了
	string preProcess(const string& s)
	{
		int n = s.size();
		// 如果字符串为空，直接返回空字符
		if (n == 0) return "";

		string ret = "^";
		for (int i = 0; i < n; i++)
		{
			ret += "#" + s.substr(i, 1);
		}
		ret += "#$";
		return ret;
	}
};

C版：

#define min(a,b) ((a) < (b)?(a):(b))
char* longestPalindrome(char* s) {
	int len = strlen(s);
	int str_len = 2 * len + 1;
	char* str = (char*)malloc(sizeof(char) * (str_len));
	int* rd = (int*)malloc(sizeof(int) * (str_len));
	char* res = (char*)malloc(sizeof(char) * len + 1);

	int po = 0, max_len = 0, start = 0, p = 0;

	for (int i = 0; i < len; i++)
	{
		str[2 * i] = '#';
		str[2 * i + 1] = s[i];
	}
	str[str_len - 1] = '#';

	rd[0] = 1;

	for (int i = 1; i < str_len; i++)
	{
		rd[i] = i < p ? min(rd[2 * po - i], p - i) : 1;
		while (i + rd[i] < str_len && i - rd[i] >= 0 && str[i + rd[i]] == str[i - rd[i]])
			rd[i]++;
		if (i + rd[i] > p)
		{
			p = i + rd[i];
			po = i;
		}

		if (rd[i] - 1 > max_len)
		{
			max_len = rd[i] - 1;
			start = (i - max_len) / 2;
		}
	}


	for (int i = 0; i < max_len; i++)
	{
		res[i] = s[start + i];
	}
	res[max_len] = '\0';
	return res;
}