1. 問題定義
最長回文字符串問題:給定一個字符串甘畅，求它的最長回文子串長度城榛。
如果一個字符串正著讀和反著讀是一樣的，那它就是回文串孙乖。
舉個?? :
-
s="ababa", 最長回文長度為5浙炼；即ababa -
s="abccb", 最長回文長度為4，即bccb唯袄。
2.暴力解法:
對于最長回文子串問題弯屈，最簡單粗暴辦法是:找到所有字符串的子串，遍歷每一個子串以驗證它們是否為回文串恋拷。一個子串由子串的起點和終點確定资厉，因此對于一個長度為n的字符串，共有n^2個子串蔬顾。這些子串的平均長度大約為n/2宴偿，因此這種解法的時間復雜度是O(n^3)湘捎。
解法：
string findLongestPalindrome(string &s){
if (s.empty()) {
return "";
}
if (s.size() == 1) {
return s;
}
// 字符串 長度
unsigned long length = s.size();
// 最長 回文 字符串 長度
int maxLength = 0;
// 最長 回文 字符串 起始地址
int start = 0;
for(int i = 0; i < length; i++){
for (int j = i + 1; j < length; j++) {
int tmp1, tmp2;
// 判斷 是不是 回文
for (tmp1 = i, tmp2 = j; tmp1 < tmp2; tmp1++, tmp2--) {
if(s.at(tmp1) != s.at(tmp2)){
break;
}
}
// 如果 遍歷 到中間 說明這是一個 回文 字符串
if (tmp1 >= tmp2 && (j-i) >= maxLength) {
maxLength = j - i + 1;
start = i;
}
}
}
if (maxLength > 0) {
return s.substr(start, maxLength);
}
return "";
}
3. 動態(tài)規(guī)劃
回文字符串的子串也是回文，所以對于母串s,我們用p[i][j] = 1(表示以i開始以j結(jié)束的子串)是回文字符串窄刘，那么p[i+1][j-1]也是回文字符串窥妇。
這樣當
s[i] = s[j]時，如果p[i+1][j-1]是回文子串娩践，則p[i][j]也是回文子串活翩。如果
p[i+1][j-1]不是回文子串或者s[i] != s[j],那么p[i][j]就不是回文子串。-
特別地翻伺，對于這樣的字符串——只包含單個字符材泄、或者兩個字符重復，其均為回文串
p[i][i] = 1; c[i][i+1] = 1吨岭， if(s[i] == s[i+1]) -
這樣需要額外的空間
o(N^2),算法復雜度也是o(n^2).
解法:static int const arrayLength = 100; string findLongestPalindrome(string &s){ if (s.empty()) { return ""; } if (s.size() == 1) { return s; } // 字符串 長度 unsigned long length = s.size(); // 最長 回文 字符串 長度 int maxLength = 0; // 最長 回文 字符串 起始地址 int start = 0; // 存儲 所有 子字符串 bool p[arrayLength][arrayLength] = {false}; for(int i = 0; i < length; i++){ // 單個 字符 為 回文串 p[i][i] = true; // 判斷 兩個字 重復 情況 if ((i < length - 1) && s.at(i) == s.at(i+1)) { p[i][i + 1] = true; start = i; maxLength = 2; } } // 子串 長度(因為已經(jīng)計算了單個或兩個字重復的回文字符串,所以子串長度最低從3開始) // 計算 3 - length 所有子串中 所有最長子串 for(int len = 3; len <= length; len++){ // 子串 起始 地址 // 在 字符串 中 找到 所有 長度為 len的子串并判斷 for (int i = 0; i <= length - len; i++) { int j = i + len - 1; if (p[i+1][j-1] && s.at(i) == s.at(j)) { p[i][j] = true; maxLength = len; start = i; } } } if (maxLength >= 2) { return s.substr(start, maxLength); } return ""; }
這種解法拉宗，當最大的回文子串有多個時，取最后一個辣辫，如果要取第一個旦事，則在 start = i后面加上break;即可。
C語言解法：
static int const arrayLength = 100;
/**
找到 最長 回文 子串 (動態(tài) 規(guī)劃 方法)
@param string 字符串
@param stringLength 字符串 長度
*/
void findLongestPalindromeTwo(char *string, int stringLength) {
if (string == NULL || stringLength == 0) {
return;
}
if (stringLength == 1) {
printf("%s\n", string);
return;
}
// 回文串 長度
int maxLength = 0;
// 起始 位置
int startPosition = 0;
// 輔助 數(shù)組(存儲 所有 字符串)
int helperArray [arrayLength][arrayLength] = {false};
// 循環(huán) 遍歷
for (int tmpIndex = 0; tmpIndex < stringLength; tmpIndex++) {
// 單個 字符 為 回文串
helperArray[tmpIndex][tmpIndex] = true;
if (string[tmpIndex] == string[tmpIndex + 1]) {
// 相同 字符 比如 aa 也是 回文串
helperArray[tmpIndex][tmpIndex + 1] = true;
startPosition = tmpIndex;
maxLength = 2;
}
}
// 循環(huán) 遍歷
// 子串 長度(因為已經(jīng)計算了單個或兩個字重復的回文字符串,所以子串長度最低從3開始)
// 計算 3 - length 所有子串中 所有最長子串
for (int len = 3; len <= stringLength; len ++) {
for (int i = 0; i <= stringLength - len; i ++) {
int j = i + len - 1;
if (helperArray[i + 1][j - 1] == true && string[i] == string[j]) {
helperArray[i][j] = true;
maxLength = len;
startPosition = i;
}
}
}
if (maxLength > 1) {
for (int tmpIndex = 0; tmpIndex < maxLength; tmpIndex++) {
printf("%c", string[startPosition]);
startPosition++;
}
printf("\n");
}
}
4.中心擴展
很明顯所有的回文字符串都是對稱的;
長度為奇數(shù)回文字符串以最中間字符位置為對稱軸左右對稱络它。
長度為偶數(shù)的回文串以中間兩個字符的空隙為對稱軸對稱族檬。
因此，整個字符串中所有字符化戳，以及字符間的空隙都有可能是某個回文子串的對稱軸位置单料。可以遍歷這些位置点楼，在每個位置上同時向左向右擴展扫尖，直到左右兩邊字符不同或者到達邊界。
對于一個長度為n的字符串掠廓，這樣的位置一共有
n+n-1=2n-1個换怖，在每個位置上平均要進行大約n/4次比較，此算法的時間復雜度為o(n^2).
解法：
string findLongestPalindrome(string &s) {
if (s.empty()) {
return "";
}
if (s.size() == 1) {
return s;
}
unsigned long length = s.size();
int maxlength = 0;
int start = 0;
string tmpStr = s;
for(int i = 0,k = 0; i <= length; i++){
s.insert(k, "#");
k = k + 2;
}
for (int i = 0 ; i < length; i++) {
// 間隔 兩個 字符
int j = i - 1, k = i + 1;
while (j >= 0 && k < length && s.at(j) == s.at(k)) {
if ((k - j + 1) > maxlength) {
maxlength = k - j +1;
start = j;
}
j--;
k++;
}
}
if(maxlength > 0){
int tmpMaxLength = (maxLength - 1)/2;
int tmpStartPostion = start/2;
return tmpStr.substr(tmpStartPostion,tmpMaxLength);
}
return "";
}
C語言解法:
/**
找到 最長 回文 子串 (中心 對稱 方法)
@param string 字符串
@param stringLength 字符串 長度
*/
void findLongestPalindrome(char *string, int stringLength) {
if (string == NULL || stringLength == 0) {
return;
}
if (stringLength == 1) {
printf("%s\n", string);
return;
}
// 插入 特殊字符 后字符串 長度
int tmpStringLength = stringLength * 2 + 1;
// 開辟 新的字符串
char *tmpString = malloc(sizeof(char) * tmpStringLength);
// 新字符串 復制 舊字符串 并在空隙插入 '#'
tmpString[0] = '#';
for (int tmpIndex = 0; tmpIndex < stringLength; tmpIndex ++) {
tmpString[tmpIndex * 2 + 1] = string[tmpIndex];
tmpString[tmpIndex * 2 + 2] = '#';
}
// 回文串 長度
int maxLength = 0;
// 起始 位置
int startPosition = 0;
// 遍歷 字符串
for(int i = 0; i < tmpStringLength; i++) {
int j = i - 1;
int k = i + 1;
while (j >= 0 && k < tmpStringLength && tmpString[j] == tmpString[k]) {
if (k - j + 1 > maxLength ) {
maxLength = k - j + 1;
startPosition = j;
}
j --;
k ++;
}
}
if (maxLength > 1) {
int tmpMaxLength = (maxLength - 1)/2;
int tmpStartPostion = startPosition/2;
for (int tmpIndex = 0; tmpIndex < tmpMaxLength; tmpIndex++) {
printf("%c", string[tmpStartPostion]);
tmpStartPostion++;
}
printf("\n");
}
}
5. Manacher 算法
中心擴展的算法是存在缺陷的:
由于回文字符串的奇偶性造成了不同性質(zhì)的對稱軸位置蟀瞧，因此要分兩種情況進行處理沉颂。
-
很多子串被重復多次訪問，造成較差的時間效率悦污。
舉個?? ：s : a b a b a i : 0 1 2 3 4
當i == 1和i == 2時铸屉，左邊的子串a(chǎn)ba分別被遍歷了一次。
A. 解決長度奇偶性帶來的對稱軸位置問題
Manacher算法首先對字符串做一個預處理切端，在所有的空隙位置(包括首尾)插入同樣的符號彻坛，要求這個符號是不會出現(xiàn)在原串中出現(xiàn)的，這樣會使得所有的串都是奇數(shù)長度的。已插入#號為例昌屉。
aba ———> #a#b#a#
abba ———> #a#b#b#a#
插入的是同樣的符號钙蒙，且符號不存在于原串，因此子串的回文性不受影響间驮，原來是回文的串躬厌，插完之后還是回文的，原來不是回文的竞帽，依然不是回文的烤咧。
B. 解決重復訪問的問題
我們把一個回文中最左或最右位置的字符與其對稱軸的距離稱為回文半徑。Manacher定義了一個回文半徑數(shù)組RL,用RL[i]表示以第i個字符為對稱軸的回文串的回文半徑抢呆。我們一般對字符串從左往右處理，因此這里定義RL[i]為第i個字符為對稱軸的回文串的最右一個字符與字符i距離笛谦。對于上面插入分隔符之后的兩個串抱虐，可以得到RL數(shù)組。
s: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6
s: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8
上面我們還求了一下RL[i]-1饥脑。通過觀察可以發(fā)現(xiàn)恳邀，RL[i]-1的值，正是在原來那個沒有插入過分割符的串中灶轰，以位置i為對稱軸的最長回文串的長度谣沸。那么只要我們求出RL數(shù)組，就能得到最長回文子串的長度笋颤。
那么問題就變成了乳附，怎樣高效地求RL數(shù)組，基本思路是利用回文串的對稱性伴澄，擴展回文串赋除。
我們再引入一個輔助變量MaxRight,表示當前訪問到的所有回文子串，所能觸及的最右一個字符的位置非凌。另外還要記錄下MaxRight對應的回文串的對稱軸所在位置,記為pos举农，它們的位置關系如下。
我們從左往右地訪問字符串來求RL,假設當前訪問到的位置是i,即要求RL[i],在對應上圖敞嗡，i必然在pos右邊颁糟，但是我們更關注的是，i是在MaxRight的左邊還是右邊喉悴，我們分情況分析棱貌。
- ** 當i在MaxRight的左邊**
如下圖所示:
我們知道，圖中兩個紅色塊之間(包括紅色塊)的串是回文的粥惧；并且以i對稱軸的回文串键畴，是與紅色塊間的回文串有所重疊的。我們找到i關于pos的對稱位置j,這個j對應RL[i]我們已經(jīng)算過的。根據(jù)回文串的對稱性起惕，以i為對稱軸的回文串和以j為對稱軸的回文串涡贱，有一部分是相同的。這里又有兩種細分情況惹想。
a. 以j為對稱軸的回文串比較短问词，短到如下圖所示:
這時我們知道
RL[i]至少不會小于RL[j],并且已經(jīng)知道了部分的以i為中心的回文串，于是我們可以令RL[i]=RL[j].但是以i對稱軸的回文串可能實際上更長嘀粱，因此我們試著以i為對稱軸激挪，繼續(xù)向左右兩邊擴展，知道左右兩邊字符不同或者到達邊界锋叨。b.以
j為對稱軸的回文串很長垄分，如下圖所示:
這時，我們只能確定娃磺，兩條藍線之間的部分(及不超過
MaxRight的部分)是回文的薄湿，于是從這個長度開始，嘗試以i為中心向左右兩邊擴展偷卧，知道左右兩邊字符不同或者到達邊界豺瘤。
綜上，我們只能獲取RL[2*pos - i]和 MaxRight-1這兩者中最小的值听诸，來保證該范圍內(nèi)的字符串是回文字符串坐求，RL[i] = min(RL[2*pos - i], MaxRight-1),之后都要嘗試更新MaxRight和pos，因為有可能得到更大MaxRight.
具體操作如下:
step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i為中心擴展回文串晌梨，直到左右兩邊字符不同桥嗤，或者到達邊界。
step 3: 更新MaxRight和pos
-
當
i在MaxRight的右邊
遇到這種情況派任，說明以i為對稱軸的回文串還沒有任何一部分被訪問過砸逊，于是只能從i的左右兩邊開始嘗試擴展了，當左右兩邊字符不同或者到達字符串邊界時停止更新掌逛。然后更新MaxRight和pos师逸。
解法:string findLongestPalindrome3(string &s) { if (s.empty()) { return ""; } if (s.size() == 1) { return s; } unsigned long length = s.size(); int MaxRight = 0; int Maxlen = 0; int pos = 0; string tmpStr = s; for(int i = 0,k = 0; i <= length; i++){ s.insert(k, "#"); k = k + 2; } length = s.size(); int *RL = new int[length](); memset(RL, 0x00, sizeof(length)); for (int i = 0; i < length; i++) { if (i < MaxRight) { RL[i] = min(RL[2*pos - i], MaxRight-1); }else { RL[i] = 1; } while (i - RL[i] >= 0 && i+RL[i] < length && s[i - RL[i]] == s[i + RL[i]]) { RL[i] += 1; } if (RL[i] + i - 1 > MaxRight) { MaxRight = RL[i] + i - 1; pos = i; } Maxlen = max(Maxlen, RL[i]); } if (Maxlen > 0) { return tmpStr.substr((pos+1)/2 - Maxlen/2, Maxlen - 1); } free(RL); return ""; }
C語言解法:
/**
找到 最長 回文 子串 (拉馬車 方法)
@param string 字符串
@param stringLength 字符串 長度
*/
void findLongestPalindromeThree(char *string, int stringLength) {
if (string == NULL || stringLength == 0) {
return;
}
if (stringLength == 1) {
printf("%s\n", string);
return;
}
// 插入 特殊字符 后字符串 長度
int tmpStringLength = stringLength * 2 + 1;
// 開辟 新的字符串
char *tmpString = malloc(sizeof(char) * tmpStringLength);
// 新字符串 復制 舊字符串 并在空隙插入 '#'
tmpString[0] = '#';
for (int tmpIndex = 0; tmpIndex < stringLength; tmpIndex ++) {
tmpString[tmpIndex * 2 + 1] = string[tmpIndex];
tmpString[tmpIndex * 2 + 2] = '#';
}
// 記錄 最長 半徑 范圍
int maxRight = 0;
// 記錄 最長 回文 字符串 長度
int maxLength = 0;
// 當前 最長 半徑 的 對稱軸
int currentPosition = 0;
// 記錄 每個 位置 最長回文 長度
int *palindromeArray = malloc(sizeof(int) * tmpStringLength);
memset(palindromeArray, 0x00, sizeof(tmpStringLength));
// 遍歷 字符串
for (int tmpIndex = 0; tmpIndex < tmpStringLength; tmpIndex++) {
// 當前 字符 在最大 半徑 范圍 左邊
if (tmpIndex < maxRight) {
if (palindromeArray[2*currentPosition - tmpIndex] > maxRight - tmpIndex) {
palindromeArray[tmpIndex] = maxRight - tmpIndex;
}
else {
palindromeArray[tmpIndex] = palindromeArray[2*currentPosition - tmpIndex];
}
}
// 當前 字符 在 最大半徑 范圍 右邊(沒有被遍歷過)
else {
palindromeArray[tmpIndex] = 1;
}
// 在先前 計算的 回文長度 基礎 上 擴展遍歷
while (tmpIndex - palindromeArray[tmpIndex] >= 0 &&
tmpIndex + palindromeArray[tmpIndex] < tmpStringLength &&
tmpString[tmpIndex - palindromeArray[tmpIndex]] == tmpString[tmpIndex + palindromeArray[tmpIndex]]) {
palindromeArray[tmpIndex] += 1;
}
if (palindromeArray[tmpIndex] + tmpIndex - 1 > maxRight) {
maxRight = palindromeArray[tmpIndex] + tmpIndex - 1;
currentPosition = tmpIndex;
}
// 更新 長度
if (maxLength < palindromeArray[tmpIndex]) {
maxLength = palindromeArray[tmpIndex];
}
}
if (maxLength) {
int tmpMaxLength = maxLength - 1;
int tmpStartPostion = (currentPosition + 1)/2 - maxLength/2;
for (int tmpIndex = 0; tmpIndex < tmpMaxLength; tmpIndex++) {
printf("%c", string[tmpStartPostion]);
tmpStartPostion++;
}
printf("\n");
}
}
C.復雜度分析:
空間復雜度:插入分隔符行程新串，占用了線性的空間大卸够臁篓像；RL數(shù)組也占用線性 大小的空間，因此空間復雜度是線性的皿伺。時間復雜度:盡管代碼里面有兩層循環(huán)员辩，由于內(nèi)層循環(huán)只是對尚未匹配的部分進行，因此對于每一個字符而言只會進行一次鸵鸥，因此時間復雜度是o(n).
