Tag Archives: 回文

LeetCode Palindromic Substrings

LeetCode Palindromic Substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won't exceed 1000.

给定一个字符串,问该字符串中有多少个回文子串。
暴力解法就是枚举每个子串,判断子串是否是回文串。判断一个字符串是否是回文串,可以用首尾指针法,也可以用中心扩展法,方法很多,需要O(n)时间,所以暴力总时间是O(n^3)。
稍微高效一点的方法是,不枚举子串,直接对每个字符用中心扩展法,请看讨论区代码
我的解法是O(n^2)的DP方法,dp[i][j]表示子串[i,j]是否是回文串。首先对于长度为1的子串dp[i][i]=1肯定都是回文串;求dp[i][j]时,如果s[i]==s[j]且dp[i+1][j-1]是回文串,则dp[i][j]=1也是回文串。
最后统计一下dp数组中有多少个1就有多少个回文子串。
代码如下:

class Solution {
public:
	int countSubstrings(string s) {
		int ans = 0, n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		for (int i = 0; i < n; ++i) {
			dp[i][i] = 1;
			++ans;
		}
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len - 1;
				if (j >= n)break;
				if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
					dp[i][j] = 1;
					++ans;
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时12MS。

LeetCode Palindrome Partitioning

LeetCode Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

本题要求把字符串s分割成若干个子串,使得每个子串都是回文串。如果有多种分割方法,输出所有的分割方案。
很有意思的一道题。我是这样做的:首先用DP求出任意一个子串s[i,...,j]是否为回文串,这就相当于知道了s中那几个位置可以切割;然后就在s中DFS每个割点,求出所有的分割方案。
DP求s[i,...,j]是否为回文串的过程是这样的,如果s[i]==s[j],且dp[i+1][j-1]也是回文串,则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串,然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。
求到了任意一个子串是否为回文串之后,DFS每个割点就好了,这个和枚举排列情况很类似,就不再赘述了。完整代码如下:

class Solution {
private:
	void helper(const string& s, vector<vector<int>>& dp) {
		int n = s.size();
		for (int i = 0; i < n; ++i)dp[i][i] = 1; // 单个字符自身就是回文串
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i + len - 1 < n; ++i) {
				if (s[i] == s[i + len - 1] && ((i + 1 <= i + len - 2 && dp[i + 1][i + len - 2] == 1) || i + 1 > i + len - 2)) {
					dp[i][i + len - 1] = 1;
				}
			}
		}
	}
	void dfs(const string& s, vector<vector<int>>& dp, vector<vector<string>>& ans, vector<string>& cand,int idx) {
		if (idx == s.size()) {
			ans.push_back(cand);
			return;
		}
		for (int i = idx; i < s.size(); ++i) {
			if (dp[idx][i] == 1) {
				cand.push_back(s.substr(idx, i - idx + 1));
				dfs(s, dp, ans, cand, i + 1);
				cand.pop_back();
			}
		}
	}
public:
	vector<vector<string>> partition(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		helper(s, dp);
		vector<vector<string>> ans;
		vector<string> cand;
		dfs(s, dp, ans, cand, 0);
		return ans;
	}
};

本代码提交AC,用时6MS。

LeetCode Longest Palindromic Subsequence

LeetCode Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".


求一个字符串的最长回文子序列
使用DP求解,假设dp[i][j]表示原字符串范围[i,j]中的最长回文子序列的长度。则如果s[i]==s[j],则dp[i][j]=dp[i+1][j-1]+2,即是临近内层的最长回文子序列长度加2。如果s[i]!=s[j],则dp[i][j]=max(dp[i][j-1],dp[i+1][j]),即是左端或者右端最长回文子序列长度的最大值。
初始时dp[i][i]=1,即单个字符自成回文,长度为1。
代码如下:

class Solution2 {
public:
	int longestPalindromeSubseq(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		for (int i = n - 1; i >= 0; --i) {
			dp[i][i] = 1;
			for (int j = i + 1; j < n; ++j) {
				if (s[i] == s[j])dp[i][j] = dp[i + 1][j - 1] + 2;
				else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
			}
		}
		return dp[0][n - 1];
	}
};

本代码提交AC,用时68MS。
上述计算有些区间会重复计算dp[i][j],可以用递归方法求解,并且把计算过的值记录下来,下次遇到查询时直接返回。代码如下:

class Solution {
private:
	int helper(int l, int r, const string &s, vector<vector<int>> &dp) {
		if (l > r)return 0;
		if (l == r)return 1;
		if (dp[l][r] != 0)return dp[l][r];
		if (s[l] == s[r])dp[l][r] = helper(l + 1, r - 1, s, dp) + 2;
		else dp[l][r] = max(helper(l, r - 1, s, dp), helper(l + 1, r, s, dp));
		return dp[l][r];
	}
public:
	int longestPalindromeSubseq(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		return helper(0, n - 1, s, dp);
	}
};

本代码提交AC,用时49MS。
参考:https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution/2

LeetCode Longest Palindrome

LeetCode Longest Palindrome
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:

Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

题意:给定一个字符串,现要从字符串中抽取若干个字符,构成一个回文串,问最长能构成多长的回文串。
回文串有两种形式,偶数型abba和奇数型abcba,所以我们先hash统计每个字符出现的次数,然后对于偶数的字符可以直接全拿来用,对于奇数的字符,减1之后只拿偶数个字符,但是我们最后还可以把减去的那个字符拿回来构成奇数型回文串,但也就只能拿回一个字符,所以要提前做好标记。
完整代码如下:

class Solution {
public:
	int longestPalindrome(string s) {
		unordered_map<char, int> hash;
		for (int i = 0; i < s.size(); ++i) {
			++hash[s[i]];
		}
		int ans = 0;
		int odd = 0;
		unordered_map<char, int>::iterator it = hash.begin();
		while (it != hash.end()) {
			if ((it->second) & 1) {
				odd = 1;
				ans += it->second - 1;
			} else {
				ans += it->second;
			}
			++it;
		}
		return ans + odd;
	}
};

本代码提交AC,用时9MS。

LeetCode Palindrome Linked List

LeetCode Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?


本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组,可以直接访问数组的头尾元素,但是链表不可以随机访问。
仔细观察一下,下面两条回文链表:

  1. 1->2->3->4->5->4->3->2->1
  2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍,如果读得的结果一样就是回文,比如第1条回文,从左往右是123454321,从右往左也是123454321,所以它是回文。
但是其实我们可以不用完整读一遍,我们只读一半就可以了,比如回文1的前半部分是1234,后半部分是4321,前半部分顺着读和后半部分倒着读都是1234,这样就足以说明是回文串了。
紧接着,对于链表,我们就有这样一种解题思路:首先找到链表的中间节点,然后把后半部分链表逆序,最后看看逆序的后半部分和顺序的前半部分是否相同。
找链表的中间节点的常规思路就是快慢指针,这个在很多题中都用到了,需要指出的是,回文链表有两种情况,一种是形如1的奇数个元素,另一种是形如2的偶数个元素。如果用快慢指针找中点,1能找到真正的中点5,2能找到前一个中点4,所以我们判断回文的时候,只需要把中点后面的链表逆序,然后只比较后半部分的链表元素。比如1的情况,逆序后半部分之后得到1->2->3->4,那么前半部分也只需要比较1->2->3->4,不需要比较5,因为这是奇数链表的中点,前后链表共享的元素;2的情况,逆序后半部分之后得到1->2->3->4,前半部分也是1->2->3->4,偶数长度的情况就会把中间的两个元素分到前后两部分。
完整代码如下:

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		ListNode *faster = head, *slower = head;
		while (faster->next != NULL&&faster->next->next != NULL) {
			faster = faster->next->next;
			slower = slower->next;
		}
		//bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
		ListNode *head2 = slower, *prior = slower->next, *tail;
		head2->next = NULL;
		while (prior != NULL) { // 逆序后半段链表
			tail = prior->next;
			prior->next = head2->next;
			head2->next = prior;
			prior = tail;
		}
		head2 = head2->next;
		while (head2 != NULL) {
			if (head->val != head2->val)return false;
			head = head->next;
			head2 = head2->next;
		}
		return true;
	}
};

本代码提交AC,用时25MS。

LeetCode Valid Palindrome

LeetCode Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.


本题要判断一个字符串是否是回文串,回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时,只考虑数字和字母,并且忽略字母的大小写。
思路很简单,两个指针i,j,分别指向字符串的头尾,各自跳过所有非数字和字母的字符,然后把大写字母转换为小写字母,如果出现头尾字符不一样的情况,则不是回文,立即返回false。如果比完整个字符串都相等,则是回文,返回true。
完整代码如下:

bool isAlphaNum(char c) {
	return (c >= 'A'&&c <= 'Z') || (c >= 'a'&&c <= 'z') || (c >= '0'&&c <= '9');
}
char upper2lower(char c) {
	if (c >= 'A'&&c <= 'Z')return c + 32;
	return c;
}
class Solution {
public:
	bool isPalindrome(string s) {
		int i = 0, j = s.size() - 1;
		while (i < s.size() && j >= 0) {
			while (!isAlphaNum(s[i]) && i < s.size())i++;
			if (i >= s.size())break;
			char c1 = upper2lower(s[i]);
			while (!isAlphaNum(s[j]) && j >= 0)j--;
			if (j < 0)break;
			char c2 = upper2lower(s[j]);
			if (c1 != c2)return false;
			i++;
			j--;
		}
		return true;
	}
};

本代码提交AC,用时12MS。
二刷。其实i,j不用走完全程,只需要走到他们交错之后就可以了,也就是只需要判断整个字符串的前半段和后半段是否逆序相等。
至于代码,其实就是把while循环和if条件判断改一下,如下:

bool isAlphaNum(char c) {
    return (c >= 'A'&&c <= 'Z') || (c >= 'a'&&c <= 'z') || (c >= '0'&&c <= '9');
}
char upper2lower(char c) {
    if (c >= 'A'&&c <= 'Z')return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i <= j) {
            while (!isAlphaNum(s[i]) && i <= j)i++;
            if (i > j)break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && i <= j)j--;
            if (i > j)break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)return false;
            i++;
            j--;
        }
        return true;
    }
};

本代码提交AC,用时9MS。

LeetCode Palindrome Partitioning II

LeetCode Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


动态规划题目,类似于矩阵链相乘。设dp[i][j]表示s[i,...,j]是否为回文串,cut[j]表示s[1,...,j]需要多少刀才能切成回文串。动态规划运行到最后返回cut[n]。
对于cut[j],切第一刀的时候,我们尝试前面j个切割位点,比如我们尝试切第i点,则s[1,...,j]被分成了s[1,...,i-1]和s[i,...,j],如果s[i,...,j]为回文串,则s[i,...,j]不需要再切了,又因为cut[i-1]我们之前已经算过了,所以在i处切一刀,有cut[j]=cut[i-1]+1。尝试所有的切割位点i,找最小的cut[j]。
如果发现i=1的时候s[i,...,j]为回文串,则s[1,...,j]不需要再切了,所以cut[j]=0。
完整代码如下:

class Solution {
public:
	int minCut(string s) {
		int n = s.size();
		vector<vector<bool>> dp(n, vector<bool>(n, false));
		for (int i = 0; i < n; i++)
			dp[i][i] = true;
		vector<int> cut(n, 0); // # of cut for s[0,j]
		for (int j = 0; j < n; j++)
		{
			cut[j] = j; // set maximum # of cut
			for (int i = 0; i <= j; i++)
			{
				if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]))
				{
					dp[i][j] = true;
					if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
						cut[j] = min(cut[j], cut[i - 1] + 1);
					else // if [0...j] is palindrome, no need to cut
						cut[j] = 0;
				}
			}
		}
		return cut[n - 1];
	}
};

本代码提交AC,用时84MS。
二刷。参考讨论区一个大神的做法:https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space。这种方法不需要上面的做法的dp数组,效率也会高很多。
还是需要cuts数组,cuts[i]表示前i个字符切成回文子串,最少的刀数。对于每一个字符,我们枚举以该字符为中心,能够扩展到的最长的回文子串的长度,比如下图,以b为中心扩展,扩展到aba是一个回文子串,那么要把Y切成回文子串,需要的刀数不超过把X切成回文子串需要的刀数加1,也就是cuts[Y]=min(cuts[Y],cuts[X]+1)。
注意,扩展的时候,需要考虑到以b为中心的回文子串的长度是奇数还是偶数。

.......aba...
|<-X->| ^
|<---Y-->|

通过枚举每一个回文中心点,我们可以算到所有的cuts,最后返回cuts[n]。完整代码如下:

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串,最少的刀数
        for(int i = 0; i <= n; ++i) cuts[i]  = i - 1;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; i - j >= 0 && i + j < n && s[i - j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1);
            for(int j = 1; i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j + 1] + 1);
        }
        return cuts[n];
    }
};

本代码提交AC,用时6MS,神速。

LeetCode Palindrome Number

LeetCode Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.

这一题很有意思,要我们判断一个整数是否是回文数。
首先负数不是回文数,个位数是回文数。但是怎样判断大于9的整数是否是回文数呢?
首先想到的是把int转换为string表示,这样就很方便判断了,但是题目要求不能用额外的存储空间,也就是不能用和x位数线性以上的存储空间,当然几个常数空间是可以的。
后来想依次取出数字的首尾数字,判断是否相等。但是中间有0出现时会有问题,比如1000021,去掉首尾1之后只剩int x=2了,导致判断错误。
还有一个办法是将x转换为x的逆序x',然后依次判断x和x'的末尾是否相等,但是x'可能超出int表示范围,又作罢。
后来观察发现,回文数字765567在转换为逆序数的过程中,肯定有某个状态,x==x',比如765=765,而这时x'肯定不会超出int的表示范围。所以我们可以在边逆序的时候边判断。
完整代码如下:

class Solution {
public:
	bool isPalindrome(int x) {
		if (x < 10)
			return x >= 0;
		if (x % 10 == 0)
			return false;
		int y = 0;
		while (x > y)
		{
			y = y * 10 + x % 10;
			if (x == y) //76567
				return true;
			x /= 10;
			if (x == y) //765567
				return true;
		}
		return false;
	}
};

本代码提交AC,用时76MS。

LeetCode Longest Palindromic Substring

LeetCode 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中的最长回文子串,之前在hihoCoder 1032-最长回文子串就详细讨论过相关问题,这里就不再赘述了,代码完全一样,如下:

class Solution {
public:
	string preProcess(string s)
	{
		int n = s.size();
		if (n == 0)
			return "^#";
		string ret = "^";
		for (int i = 0; i < n; i++)
			ret += "#" + s.substr(i, 1);
		return ret + "#$";
	}
	string longestPalindrome(string s) {
		string t = preProcess(s);
		vector<int> p(t.size(), 0);
		int c = 0, r = 0, n = t.size();
		for (int i = 1; i < n - 1; i++)
		{
			int i_mirror = 2 * c - i;
			p[i] = (r > i) ? min(p[i_mirror], r - i) : 0;
			while (t[i + p[i] + 1] == t[i - p[i] - 1])
				p[i]++;
			if (i + p[i] > r)
			{
				c = i;
				r = i + p[i];
			}
		}
		int maxLen = 0, centerIndex = 0;
		for (int i = 1; i < n - 1; i++)
		{
			if (p[i] > maxLen)
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}
		return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
	}
};

本代码提交AC,用时12MS,击败了73%的CPP用户,看来效率不错,估计中心扩展法O(n^2)也能过。

hihoCoder 1032-最长回文子串

hihoCoder 1032-最长回文子串
#1032 : 最长回文子串
时间限制:1000ms
单点时限:1000ms
内存限制:64MB
描述
小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。
这一天,他们遇到了一连串的字符串,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能分别在这些字符串中找到它们每一个的最长回文子串呢?”
小Ho奇怪的问道:“什么叫做最长回文子串呢?”
小Hi回答道:“一个字符串中连续的一段就是这个字符串的子串,而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串,所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”
小Ho道:“原来如此!那么我该怎么得到这些字符串呢?我又应该怎么告诉你我所计算出的最长回文子串呢?
小Hi笑着说道:“这个很容易啦,你只需要写一个程序,先从标准输入读取一个整数N(N<=30),代表我给你的字符串的个数,然后接下来的就是我要给你的那N个字符串(字符串长度<=10^6)啦。而你要告诉我你的答案的话,只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了!你看这就是一个例子。”
提示一 提示二 提示三 提示四
样例输入
3
abababa
aaaabaa
acacdas
样例输出
7
5
3


这个题目有很多解法,具体可以看这里,其中的中心扩展法很有意思,不过时间复杂度O(n^2)。后来发现Manacher算法时间复杂度只要O(n),膜拜之,无奈研究了很久也没理解,很多中文博客写得不够全面详细,直到我看了这篇文章,明白了。主要思路如下:
1. 首先将字符串S预处理成T。在S的字符之间插入#字符,如下:

For example: S = “abaaba”, T = “#a#b#a#a#b#a#”.

这样之后,不管S长度是奇数还是偶数,得到的T都是奇数,这样就不需要分情况讨论了,也方便了后面的求解。
2. 我们将中间结果存储在数组P中:

T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

P[i]表示以T[i]为中心,T中回文串的半径,比如T[3]=b,P[3]=3,表示以b为中心,T中回文串的半径为3,也就是#a#b#a#,半径就是#a#,而P[3]=3也正好是原始串S中以b为中心的回文串的总长度,即回文串aba的长度为3.
所以我们只需要求出数组P,然后求P中的最大值即为S中最长回文串的长度。
3. 为了求数组P,有两种情况需要讨论。假设我们已经求出一部分数组P的值了,如下图所示:
C为目前P中最大值的位置,C为目前T中使得R推进到最右边的回文串的中心位置center(不一定是P的最大值的位置,最大值还需要在最后一步求解),它的半径是9,所以左边(Left)到达L,右边(Right)到达R,下标分别是2和20.
4. 第一种情况是,如果此时i=13,则P[13]等于多少呢?

i的对称点i'下标为9,P[i']=1,它的回文串没有超出以C为中心的回文串,根据对称性,则P[i]=P[i']=1.
5. 第二种情况是,如果i=15,则P[15]等于多少呢?

由图可知,i的对称点i'=7,P[i']=7,即以i'为中心的回文串已经超出了以C为中心的回文串,L左边的红色线条即为超出部分。那么此时不能说P[i]=P[i']=7,因为如果这样的话,那么以C为中心的回文串也可以扩展到红色线条部分,这样P[C]就大于原来的P[C]了。但是可以肯定的是,i的半径至少是R-i=5,所以我们可以在此基础上依次增加i的半径,判断是否还是回文串。
6. 总结一下就是:

if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to find P[ i ].

更详细的解释和部分代码实现请看原博文,下面是我的针对hihoCoder #1032 : 最长回文子串提交的代码:

#include&lt;iostream&gt;
#include&lt;string&gt;
using namespace std;
//字符串预处理,插空#,首尾分别^&amp;
string pre_process(string s)
{
     string rs;
     int s_len=s.size();
     if(s_len==0)
          return "^&amp;";
     rs="^";
     for(int i=0;i&lt;s_len;i++)
          //rs+="#"+s[i];//const char* 和int/char不能相加,指针越界
          rs+="#"+s.substr(i,1);//const char*和string可以相加
     return rs+"#&amp;";
}
int get_longest_pal_len(string s)
{
     string T=pre_process(s);
     int n=T.size();
     int *P=new int[T.size()];
     P[0]=0;
     int C=0,R=0;
     for(int i=1;i&lt;n-1;i++) {
          int i_mirror=2*C-i;//i的对称位置
          P[i]=(R&gt;i)?min(R-i,P[i_mirror]):0;//如果R&gt;i,说明i还在R里面,如果P[i_mirror]&lt;=R-i,则类似图中i=13;如果P[i_mirror]&gt;R-i,则P[i]至少是R-i的,然后从R-i递增测试
          while(T[i+1+P[i]]==T[i-1-P[i]])
               P[i]++;
          if(i+P[i]&gt;R)//更新最大的中心点和右边界
          {
               C=i;
               R=i+P[i];
          }
     }
     int max_len=0;
     for(int i=1;i&lt;n-1;i++) {
           if(P[i]&gt;max_len)//寻找最大P[i],P[i]既是T[i]的回文串半径(包含#),也是以S[i]为中心的最长回文串长度。
               max_len=P[i];
     }
     delete[] P;
     return max_len;
}
int main()
{
     int n;
     string s;
     cin&gt;&gt;n;
     while(n--)
     {
          cin&gt;&gt;s;
          cout&lt;&lt;get_longest_pal_len(s)&lt;&lt;endl;
     }
     return 0;
}

这段代码有一小部分需要注意一下,就是string pre_process(string s);字符串预处理函数中的rs+="#"+s.substr(i,1);不要写成了rs+="#"+s[i];,因为"#"会隐式转换成const char*类型,而s[i]是char/int类型,"#"+s[i]相当于指针增加一个int偏移量,会导致指针越界。所以要写成"#"+s.substr(i,1),因为string.substr返回的是string类型,const char*和string是可以相加(连接)的。看来我还是基础不牢啊~