1. 前言
我們可以用O(n^2)暴力求解最長回文子串。
之是以是這個複雜度,是因為我們對每個字元比較其兩邊元素是否相等時,我們都是從它最旁邊的一個開始疊代的。
但如果我們能以該字元為中心,其附近的某一段子串已為回文,在此基礎上比較更遠的元素,那麼就有可能降低這個複雜度了。
2. 定義及預處理
将字串str擴充成string s(2*str.size()+1), 在str的兩端及每個字元間加上個特殊符号,在此使用#
如str = "axamppm", 則s = "#a#x#a#m#p#p#m#".
這樣的好處是可以同時處理回文長度為奇數或偶數的情況:因為奇數回文的中心是一個字元,偶數的則為兩個字元。在擴充後得s中,最長回文子串的中心一定為一個字元(特殊字元# 或 原本str中的字元)
定義輔助數組vector<int> p(2*str.size()+1), p表示:字串s中對應下标的字元 在s中向右延伸仍為回文的最長長度。如
s: # a # x # a # m # p # p # m #
p: 1 2 1 3 1 2 1 2 1 2 4 2 1 2 1
mx為在目前疊代i之前,x+p[x]的最大值(即最遠長度)
id為取得mx的x值。
3. 性質
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICdzFWRoRXdvN1LclHdpZXYyd2LcBzNvwVZ2x2bzNXak9CX90TQNNkRrFlQKBTSvwFbslmZvwFMwQzLcVmepNHdu9mZvwFVywUNMZTY18CX052bm9CXuVjMiNTOsJGbod0YsJ1MjZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39DO3AjMwkDM0ADMyYDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
如圖1所示,mx > i, 且mx > i + p[j] (這個限制在圖2中解釋)
由于id一定在i左邊,且以j為中心的回文串完全處在一個回文串的左半部分。那麼其對稱點i有性質 p[i] = p[j].
我們即可以結束這次疊代,考察下一個點i+1.
圖2為 mx > i, 且mx < i + p[j]的情況
此時因為以 j 為中心的最長回文串隻是部分處在一個回文串的左半部分。那麼其對稱點i有性質 p[i] = mx - i;
此時因繼續比較s[ i-p[i]-1 ]及s[ i+p[i]+1 ]的大小。
for ( ; i-p[i]-1>=0 && i+p[i]+1<str.size()
&& str[i-p[i]-1] == str[i+p[i]+1]; ++ p[i]) {}
在疊代結束後,更新mx及id.
4. 代碼實作
class Solution
{
public:
string longestPalindrome(string s)
{
string str(2*s.size()+1, 0);
// str
for (size_t i = 0, j = 0; i < str.size(); ++ i)
{
if (i % 2 == 0)
{
str[i] = 0;
} else
{
str[i] = s[j ++];
}
}
// p
int mx = 0, id, max_length=0, max_id;
vector<int> p(2*s.size()+1, 0);
for (int i = 0; i < str.size(); ++ i)
{
p[i] = mx>i? min(p[2*id-i], mx-i): 0;
for ( ; i-p[i]-1>=0 && i+p[i]+1<str.size()
&& str[i-p[i]-1] == str[i+p[i]+1]; ++ p[i]) {}
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
if (max_length < p[i])
{
max_length = p[i];
max_id = i;
}
}
return s.substr((max_id-p[max_id])/2, p[max_id]);
}
};
5. 複雜度證明
考察每次疊代,
當mx > i時,
圖1的情況,p[i] = p[j]後疊代結束,O(1)
圖2的情況,初始化p[i] = mx - i, 之後每次運算都将移進mx.
當mx < i時,
若中心點i左右比對不成功,疊代結束,O(1)
若比對成功,每次運算都将移近mx.
是以隻有O(N)次比對失敗,此外每次成功比對,都将移近mx. mx共移進O(N)
由此複雜度為O(N)