Manacher

Manacher 是一種 \(O(n)\) 的回文串查找方式.

樸素算法

長度為 \(n\) 的字符串最多有 \(n^2\) 個回文子串. 樸素算法枚舉回文串的中心。樸素算法復雜度為 \(O(n^2)\) .

int find(string s){
	for (int i=0;i<s.size();i++){
		d1[i]=1;
		while(0<=i-d1[i] && i+d1[i]<s.size() && s[i-d1[i]]==s[i+d1[i]]){
			d1[i]++;
		}
		d2[i]=0;
		while(0<=i-d2[i]-1 && i+d2[i]<s.size() && s[i-d2[i]-1]==s[i+d2[i]]){
			d2[i]++;
		}
	}
}

其中 \(d1_i\) 表示以 \(i\) 為中心的奇回文串的數量， \(d2_i\) 表示以 \(i-1,i\) 為中心的偶回文串的數量。

Manacher算法

Manacher算法的核心在于記錄一個最靠右的已知回文串，再枚舉回文串右側的中心時，可以直接繼承回文串左側的中心的數據。

圖1：

\(1,\overbrace{2,\underbrace{3,4,5,6,7,8,9}_{\text{回文串，大小為7}},10,\underbrace{11,12,13,14,15,16,17}_{\text{繼承前文的回文串，大小最大為7}},18}^{\text{回文串}},19,20\)

因為右側回文串在大回文串內，所以與左側對稱，無法再延伸。

圖2：

\(1,\overbrace{\underbrace{2,3,4,5,6,7,8,9}_{\text{回文串，大小為8}},10,\underbrace{11,12,13,14,15,16,17,18}_{\text{繼承前文的回文串，大小最小為8}}}^{\text{回文串}},19,20\)

雖然右側回文串在大回文串下，但是右端點可以延伸到大回文串之外，可能 \(S_2 \not = S_{19}\) ，所以可以再延伸。

實現細節

為了快速計算，我們維護已找到的最靠右的子回文串的 邊界 \((l,r)\)。初始時，我們設 $l=1 $ 和 \(r=-1\)。

現在假設我們要對下一個中心 \(i\) 計算 \(d_i\) ，而之前所有 \(d_{i-1}\) 中的值已計算完畢。我們將通過下列方式計算：

• 如果 \(i\) 位于當前子回文串之外，即 \(i>r\)，那么我們調用樸素算法。然后更新最右側區間 \((l,r)\) 。

• 對于 \(i \le r\) 的情況。首先在子回文串 \((l, r)\) 中反轉位置 \(i\)，即我們得到 \(j=l+(r-i)\) 。我們從已計算過的 \(d_j\) 的值中獲取回文串大小。因為位置 \(j\) 同位置 \(i\) 對稱，我們可以置 \(d_i=d_j\) 。

• 然而對于圖二的情況：當「內部」的回文串到達「外部」回文串的邊界時，即 \(j-d_j+1 \le l\) 。因為在「外部」回文串范圍以外的對稱性沒有保證，因此直接置 \(d_i=d_j\) 將是不正確的。為了正確處理這種情況，我們應該置 \(d_i=r-i\)。之后我們將運行樸素算法以嘗試盡可能增加 \(d_i\) 的值。最后更新最右側區間 \((l,r)\) 。

Manacher復雜度

考慮到每次執行樸素算法都會更新右端點 \(r\) ，所以實際算法復雜度為 \(O(n)\) 。

代碼:

vector<int> d1(n);
int l=0,r=-1;
for(int i=0;i<n;i++){
	if(i>r) k=1;
	else k=min(d1[l+r-i],r-i+1);
	while(0<=i-k && i+k<n && s[i-k]==s[i+k]){
		k++;
	}
	d1[i]=k--;
	if(i+k>r){
		l=i-k;
		r=i+k;
	}
}