0. 引言

●子串(substring）：原始字符串的一個連續子集;
●子序列（subsequence）：原始字符串的一個子集。

1. 什么叫回文串？

如果一個字符串正著讀和反著讀是一樣的，那它就是回文串。[1]

例如，字符串“apapa”無論從左到右還是從右到左讀取，結果均為“apapa”。以下是回文串的核心特性：

1. 對稱性
   回文串的字符序列以中心為對稱軸鏡像對稱。若字符串長度為奇數（如“radar”），對稱軸是中間字符；若長度為偶數（如“abba”），對稱軸位于中間兩個字符之間。

假如回文的中心為 雙數，例如 abba，對稱軸是中間字符為 a?bb a，

假為回文的中心為 單數，例如 abbabde, 對稱軸是中間字符為a b b?a b d e，?

?

?

1. 字符位置對應
   對于長度為n的回文串，第i個字符與第n?i+1個字符必須相同（1≤i≤n）。例如，字符串“noon”中，第1個字符“n”與第4個字符“n”對應，第2個字符“o”與第3個字符“o”對應。

2. 長度無關性
   回文串的長度可以是任意正整數，包括長度為1的字符（如“a”）或空字符串（通常也被視為回文）。

2. 代碼實現

	string longestPalindrome(string s) {if (s.length() < 1){return "";}int start = 0, end = 0;for (int i = 0; i < s.length(); i++){int len1 = expandAroundCenter(s, i, i);//一個元素為中心int len2 = expandAroundCenter(s, i, i + 1);//兩個元素為中心int len = max(len1, len2);if (len > end - start){start = i - (len - 1) / 2;end = i + len / 2;}}return s.substr(start, end - start + 1);}int expandAroundCenter(string s, int left, int right){int L = left, R = right;while (L >= 0 && R < s.length() && s[L] == s[R]){// 計算以left和right為中心的回文串長度L--;R++;}return R - L - 1;}

3. 逐行解析

string longestPalindrome(string s) 
{

• 功能：主函數，輸入字符串s，返回其中最長的回文子串。

if (s.length() < 1)
{return "";
}

• 解釋：如果字符串長度小于1（即為空），直接返回空字符串。

int start = 0, end = 0;

• 功能：start和end用于記錄當前找到的最長回文子串的起始和結束索引。

for (int i = 0; i < s.length(); i++)
{int len1 = expandAroundCenter(s, i, i); // 奇數長度回文中心int len2 = expandAroundCenter(s, i, i + 1); // 偶數長度回文中心int len = max(len1, len2);

• 功能：對每個字符i，分別計算以它為中心的奇數長度回文（len1）和以它及其下一個字符為中心的偶數長度回文（len2），取兩者中的較大值作為當前中心的最大回文長度。

if (len > end - start)
{start = i - (len - 1) / 2;end = i + len / 2;
}

• start：計算當前回文的起始位置。對于長度為len，中心點在i處，起始位置為i - (len-1)/2。
• end：計算當前回文的結束位置，為i + len / 2。

int expandAroundCenter(string s, int left, int right)
{int L = left, R = right;while (L >= 0 && R < s.length() && s[L] == s[R]){L--;R++;}return R - L - 1;
}

• 功能：以left和right為左右中心，向兩邊擴展，計算最長回文的長度。
• 過程：
  • 初始時，L = left,?R = right.
  • 當s[L] == s[R]且未超出字符串邊界時，繼續向外擴展。
  • 循環結束后，返回當前回文長度：R - L - 1.

參考文獻

[1]最長回文子串 C / C++