問(wèn)題描述：給定一個(gè)字符串，求出其最長(zhǎng)回文子串的長(zhǎng)度
例如：對(duì)于字符串s="acaacdbab"而言，其回文子串分別為"caac"和"bab"，其中最長(zhǎng)回文子串長(zhǎng)度為4
解法一：中心擴(kuò)展法
對(duì)于這樣的一個(gè)問(wèn)題，一般暴力算法主要是枚舉所有子串的中心位置给梅，并在該位置上進(jìn)行擴(kuò)展，記錄并更新最長(zhǎng)回文子串的距離双揪。代碼實(shí)現(xiàn)如下：
#include "pch.h"
#include <iostream>
using namespace std;
int LongestPalindrome(const char* s, int n) {
int i, j, c, length=0;
if (s == 0 || n < 1)
return 0;
for (i = 0; i < n; i++) {
for (j = 0; (j <= i) && (i + j <= n); j++) {
if (s[i + j] != s[i - j])
break;
c = 2 * j + 1;
}
if (length <= c)
length = c;
for (j = 0; (j <= i) && (i + j <= n); ++j) {
if (s[i - j] != s[i + j + 1])
break;
c = 2 * j + 2;
}
if (length <= c)
length = c;
}
return length;
}
int main()
{
char str[] = "acaacdbab";
cout << LongestPalindrome(str, sizeof(str) / sizeof(char) - 1) << endl;
}
從代碼實(shí)現(xiàn)上可以看出暴力算法主要存在兩個(gè)缺陷：
1动羽、由于回文子串可以分為偶回文和奇回文兩種，例如abba是偶回文渔期，其對(duì)稱(chēng)中心是bb运吓，而aba則奇回文，其對(duì)稱(chēng)中心是b疯趟，二者判斷邏輯是不同的拘哨，所以需要分開(kāi)進(jìn)行處理；
2信峻、枚舉中心采用了逐個(gè)枚舉的方式倦青，并沒(méi)有有效利用到回文子串的對(duì)稱(chēng)性，使得代碼無(wú)法高效地運(yùn)行
解法二：Manacher算法
Manacher算法是對(duì)暴力算法的一個(gè)優(yōu)化盹舞。面對(duì)暴力算法的第一個(gè)缺點(diǎn)产镐，Manacher算法采用了一種方法將所有的偶回文和奇回文都轉(zhuǎn)化成為了奇回文，從而簡(jiǎn)化了代碼的判斷邏輯踢步。具體的做法是這樣的：在字符串的首尾癣亚，以及每?jī)蓚€(gè)字符中間插入一個(gè)源字符串沒(méi)有的特殊符號(hào)，使得任意長(zhǎng)度的回文子串都可以轉(zhuǎn)化為奇回文获印。舉個(gè)例子逃糟，在源字符串中，有"cabbac"和"bab"兩個(gè)回文子串蓬豁，經(jīng)過(guò)處理后會(huì)轉(zhuǎn)變?yōu)?#c#a#b#b#a#c#"和"#b#a#b#"绰咽，全部都轉(zhuǎn)化為了奇回文。同時(shí)為了更好地處理數(shù)組的越界問(wèn)題地粪，在數(shù)組的首部添加一個(gè)哨兵位$取募。
而對(duì)于第二個(gè)缺點(diǎn)，則是通過(guò)定義了一個(gè)回文半徑數(shù)組int P[]蟆技，其中P[i]表示以字符Si為中心的最長(zhǎng)回文子串向左或向右擴(kuò)張的長(zhǎng)度玩敏，例如
在明白了如何利用P[i]求出原始回文子串的長(zhǎng)度后，算法接下來(lái)的重點(diǎn)便是如何求解P數(shù)組饭入？
Manacher算法增加了兩個(gè)變量id和mx嵌器，其中id代表最長(zhǎng)回文子串的中心字符位置，mx代表最長(zhǎng)回文子串的右邊界位置谐丢，即mx=P[id]+id爽航。因此，根據(jù)回文子串的對(duì)稱(chēng)性乾忱，我們可以得出一個(gè)重要的結(jié)論：若mx>i讥珍，則有P[i]≥min(P[2id-i],mx-i）*
證明如下：
當(dāng)mx>i時(shí)，不妨記mx的對(duì)稱(chēng)點(diǎn)為my饭耳，再令j=2*id-i串述，則回文串可分為兩種情況：
-
1、當(dāng)mx-i>P[j]寞肖，以S[j]為中心字符的回文子串被包含在以S[id]為中心字符的回文子串當(dāng)中纲酗，根據(jù)回文子串的對(duì)稱(chēng)性，必有有P[j]=P[i]新蟆，如下圖：情況1.png
-
2觅赊、當(dāng)mx-i≤P[j]時(shí)，以S[j]為中心的回文子串只有部分包含在最長(zhǎng)回文子串內(nèi)部(即圖中紅框位置)琼稻，因此可以推斷P[i]≥mx-i吮螺，至于超出mx后面的部分則需要另行匹配，如下圖：情況2.png
綜合以上兩種情況，便可以得出P[i]=min(P[2*id-i],mx-i)這一重要結(jié)論
當(dāng)mx≤i時(shí)鸠补，我們無(wú)法利用最長(zhǎng)回文子串的對(duì)稱(chēng)性對(duì)P[i]的值做出更多假設(shè)萝风，因此P[i]=1,然后繼續(xù)進(jìn)行中心擴(kuò)展匹配。
代碼實(shí)現(xiàn)：
#include "pch.h"
#include <iostream>
#include <algorithm>
using namespace std;
char str[] = "$#a#c#a#a#c#d#b#a#b#";
int Manacher(const char* str,int* P,int len) {
int mx = 0;
int id;
int max_len = 0;
for (int i = 1; i < len; i++){
if (mx > i)
P[i] = min(P[2 * id - i], mx - i);
else
P[i] = 1;
while (str[i - P[i]] == str[i + P[i]])
P[i]++;
if (P[i] + i > mx) {
mx = P[i] + i;
id = i;
}
max_len = max(max_len, P[i] - 1);
}
return max_len;
}
int main()
{
int length = sizeof(str) / sizeof(char) - 1;
int* P = new int[length];
memset(P, 0, length*sizeof(int));
cout << "最長(zhǎng)回文子串長(zhǎng)度為：" << Manacher(str, P, length) << endl;
delete[] P;
return 0;
}
算法復(fù)雜度分析
顯然紫岩，對(duì)于Manacher算法规惰，其空間復(fù)雜度為O(n)，而對(duì)于時(shí)間復(fù)雜度而言泉蝌，我們考慮以下兩種極端情況：
1歇万、字符串中不含任何回文子串琳省，例如abcdefg辨萍，在這種情況中椒楣，由于while中的條件始終不滿(mǎn)足牵舱，因此圆仔，循環(huán)執(zhí)行的次數(shù)應(yīng)當(dāng)為2(n-1)摇天，故此時(shí)時(shí)間復(fù)雜度為O(n)宠哄；
任取i∈{1,...,n+1}，都滿(mǎn)足P[i]=i制妄，id=i,mx=2i>i
因此當(dāng)i>2時(shí)掸绞，有P[i]=min(P[2id-i],mx-i)=min(P[2(i-1)-i,2(i-1)-i)成立，
令j=2id-i耕捞，則有P[j]=j衔掸，進(jìn)而有
- P1[i]=min(P[2(i-1)-i,2(i-1)-i)=min(2(i-1)-i,2(i-1)-i)=i-2
注：這是經(jīng)過(guò)if判斷語(yǔ)句后得到的P[i]初始值，為了避免和最終P[i]值相混淆俺抽，此處記為P1[i]敞映，后續(xù)均以P1[i]代表初始值，P[i]代表最終值
隨后程序進(jìn)入了while循環(huán)磷斧，由于P1[i]=i-2振愿，P[i]=i捷犹，因此可以很容易看出while循環(huán)體最多僅執(zhí)行2次，故雖然代碼有2層循環(huán)冕末，但是在最壞的情況下萍歉，內(nèi)存while循環(huán)最多對(duì)n-1個(gè)字符進(jìn)行了2次循環(huán)(當(dāng)i=1時(shí)，循環(huán)不執(zhí)行栓霜；當(dāng)i=2時(shí)翠桦，循環(huán)執(zhí)行1次)，其余字符均不進(jìn)行循環(huán)胳蛮，因此整體代碼的時(shí)間復(fù)雜度是O(n)。由于最壞與最好的情況下丛晌，代碼的時(shí)間復(fù)雜度均為O(n)仅炊，因此代碼的平均時(shí)間復(fù)雜度為O(n)。
這也正是Manacher算法的精彩之處梅桩，巧妙地利用了之前所有計(jì)算出來(lái)的P[1...i-1]的值壹粟，在每次循環(huán)中對(duì)P[i]進(jìn)行快速賦值，避免P[i]的值每次都從1開(kāi)始計(jì)算宿百，大幅削減了比較次數(shù)趁仙，最終使得求解最長(zhǎng)回文子串長(zhǎng)度達(dá)到了線性級(jí)復(fù)雜度O(n)，同樣思想也被運(yùn)用在KMP算法中犀呼。
總結(jié)：
1幸撕、對(duì)于數(shù)組，字符串的一些問(wèn)題外臂，在需要分為奇數(shù)坐儿、偶數(shù)的情況下進(jìn)行討論時(shí)，往往可以采用填充的方式，將其轉(zhuǎn)化為奇數(shù)的情況貌矿，從而簡(jiǎn)化判斷邏輯炭菌。同樣的做法也可以放入到一些樹(shù)的判斷當(dāng)中，通過(guò)填充特殊結(jié)點(diǎn)逛漫，使一棵普通二叉樹(shù)轉(zhuǎn)變?yōu)橥耆鏄?shù)黑低，甚至是滿(mǎn)二叉樹(shù)，來(lái)使得問(wèn)題簡(jiǎn)化酌毡；
2克握、對(duì)于出現(xiàn)循環(huán)嵌套，且內(nèi)層循環(huán)的判斷條件與輸入數(shù)據(jù)相關(guān)枷踏，在判斷時(shí)間復(fù)雜度時(shí)菩暗，可以考慮判斷最差與最優(yōu)情況，若最優(yōu)與最差時(shí)間復(fù)雜度相同旭蠕，則一般情況下的時(shí)間復(fù)雜度應(yīng)當(dāng)與最優(yōu)或最差的時(shí)間復(fù)雜度相同停团。(有點(diǎn)類(lèi)似于數(shù)學(xué)上的夾逼定理，可以將求時(shí)間復(fù)雜度的過(guò)程近似地看成是求極限的過(guò)程)
參考資料：
1掏熬、《Manacher 算法》：https://subetter.com/articles/manacher-algorithm.html
2佑稠、《leetCode_5_Longest_Palindromic_Substring》：http://windliang.cc/2018/08/05/leetCode-5-Longest-Palindromic-Substring/
3、《編程之法——面試和算法心得》
