字元串—馬拉車算法（求最長回文串）

作為一個字元串渣渣，對于我來說，看見此類問題總會忍不住虎軀一震。。。初次見到“求最長回文串”問題時，我腦子裡無非蹦出兩個想法：

1.用棧的結構來存儲，然後出棧看是否滿足回文串的條件（回文串定義相信大家都知道，在此就不啰嗦了）；

2.看見最長，立馬想到用動态規劃的思想，寫出狀态轉移方程，找出最優子結構。

其實這兩個思路合并起來是否可以解決問題——答案是肯定的。但這樣一來的時間複雜度和空間複雜度都是很大的（時間複雜度

文章目錄

• 字元串—馬拉車算法（求最長回文串）
• • 引入—回想KMP算法
  • 進入正題—馬拉車算法的思路
  • • 半徑數組
    • 半徑數組的計算
  • 代碼實作
  • 總結

引入—回想KMP算法

KMP算法作為《資料結構》——串一章中，最重要的一個算法，想必大部分人都不陌生。同樣的，這也是字元串問題中一個經典的将時間複雜度大大優化的經典算法。

我們先來回顧一下，KMP算法的核心是什麼——找出待比對的子串的最長公共字首，一次确立next數組，作為對位失敗後下次移位的基準。

是以說，欲解決目前字元串與其他字元串的問題，須先從自身下手——這也正是馬拉車算法的方法論。

進入正題—馬拉車算法的思路

半徑數組

首先我們都知道，回文串有兩種情況：

（1）串長為基數：如abcba，該串以c為中心點作回文分界；

（2）串長為偶數：如abccba，中心點為兩個字元的分界。

針對這兩種情況，為實作統一，先在串中每個字元間（首尾端都要插入）插入一個不沖突的特殊符号作為，例如：

原串為abbba,插入一個特殊符号#後變為a#b#b#b#a#

這樣做的目的是：插入後字元串長度肯定為奇數了（奇+偶=奇），這樣做之後就肯定不用考慮串的奇偶性了。

接下來我們與KMP的next數組一樣，引入一個概念：半徑數組

這個數組p[i]用于記錄以s[i]為中心的最長回文串的半徑（不包括p[i]本身）。當p[i]=0時，說明回文串是字元串本身。

比如，#a#b#的半徑數組為{0,1,0,1,0}

仔細體會一下，最大半徑是不是就是最大回文串的半徑？

這時我們還需注意的一點是：回文串搜尋時我們需避免越界的問題。是以還要在已經處理過一遍的字元串外頭尾加上兩個特殊符号，例如：

#a#b#變為$#a#b#*

至于為什麼計算的是半徑，在于為了友善計算邊界。

半徑數組的計算

傳統的 O ( n 2 ) O(n^2) O(n2)的做法，是以中心店開始，挨個将半徑擴張，這麼一來時間複雜度就很高，因為既要周遊、又要比對；

而馬拉車算法巧妙的借用了p[i]數組，一直不斷更新兩個變量：

（1）id:回文串的中心位置；

（2）mx：回文串的最後位置；

p[i]=min(mx-i,p[2 id-i])

想想，為什麼p[i]會如此定義？

（1）當周遊時一直都符合回文，mx-i為最壞情況下p[i]的最大值；而2id-i則為，當mx-i>p[i]時，由于對稱性，2id-i和i肯定是對稱的，是以以s[i]為中心的回文子串必包含在以s[id]為中心的回文子串中。

代碼實作

此處指給出核心代碼。并沒有使用p數組表示，但思路一緻

const maxn=10005;
const int mx=0,id=0;
int min(int &x,int &y)
{
	if (x<y) return x;
	else return y;
}
int max(int &x,&y){
	if(x>y) return x;
	else return y;
}
int Manacher(char str[],int mx,int id)
{
	int len[maxn];
	len[0]=0;
	for(int i=1;i<len;i++){
		if(i<mx) Len[i]=min(mx-i,len[2*id-i]);
		else len[i]=1;//回文串本身
		while(str[i-len[i]]==str[i+len[i]]) len[i]++;
		if(len[i]+i>mx){//越界，則一直周遊
			mx=len[i]+i;
			id=i;
			sum=max(sum,len[i]);
		}
	}
	return (sum-1;
}
           

總結

馬拉車算法與KMP算法類似，需要先對字元串内部自身進行比較，且設定一個輔助數組。雖然說相比傳統的動态規劃方法，節省了時間開銷，但在半徑數組的求值問題中也用到了dp思想。當然，半徑數組的設定也不是必要的。還有一點須注意的是，由于回文串存在奇偶性，應先對字元串進行預處理。