番外篇 · 補充說明

一. 關於Manacher Algorithm的說明：

（相關題目為005 Longest Palindromic Substring[M]）

先拋出一個思考題：為什麼較之中心拓展法，Manacher Algorithm可以起到優化的作用？

在之前的題解中，我們也曾經提過幾點，但大體上都是在闡述這種演算法的原理，對於它的優越性並沒有進行詳細的解釋。現在，我想詳細談談這種演算法究竟好在哪裡。

• 奇偶性區分規避：我們都知道，中心拓展法一定要對於迴文串的奇偶性進行考慮。但Manacher Algorithm則無需考慮這種情況。因為無論給出的字元串s的長度是奇數還是偶數，在加了"#"之後，長度都一定是奇數的。這樣就成功的規避了奇偶性的問題。
• 避免計算重複情況：如果一個給出的字元串s是諸如"bbbbbbb"，那麼採用中心拓展法會發生各個迴文串相互重疊的情況，而這個時候就會多出不必要的重複計算，Manacher Algorithm可以利用輔助數組Len[]來避免重複計算，這也是它能夠達到線性時間複雜度的最關鍵的一點。

Manacher Algorithm的詳細原理：

Manacher Algorithm定義了一個數組Len[]，用以表示字元串（這裡的字元串是經過預處理之後的字元串）的迴文半徑（我們把迴文串中最左或最右位置的字元與其對稱軸的距離稱為迴文半徑）。

Len[i]表示的是以第i個字元為對稱軸的迴文串的迴文半徑。那麼由於Len[]的特殊含義，我們只要求出Len[]中最大的那一個，並記錄下它的i值，就一定能輕鬆的找出最長的迴文子串了。

此時，問題已經轉化為了如何高效的求出Len數組中的值。

我們不妨設MiddlePoint為字元串迴文子串的有效的中心點，rightMax為MiddlePoint所對應的迴文字元串的右邊界。

在從左到右遍歷的過程中，我們會需要求出每一個 i 對應的迴文字元串長度，那麼通常會出現有些 i 的迴文長度較短，被包括在之前的較長的迴文字元串中，如果這個 i 的迴文長度我們可以通過之前的數組中的某些值來求出，那麼就起到了我上邊所說的避免重複計算的作用了。

這就要求我們來找出 Len 數組中的值的各種關係。

第一種情況是i<=rightMax：

i和j對應的兩個子迴文串被MiddlePoint所對應的子迴文串完全包括，可得Len[i]=Len[j]。

（不僅僅字元串是迴文的，它們對應的Len[]也是按照中心對稱的。）

即Len[i] == Len[2 * MddlePoint - i]。

第二種情況是i+Len[i]>rightMax，在此時，i並不在MiddlePoint所包含的迴文串範圍內，所以只能重新匹配，並更新MiddlePoint和rightMax。

二.如何不利用64位整形存儲，來解決翻轉整數問題：

（相關題目為007 Reverse Integer[E]，此處感謝提出疑問的紫月小童鞋。 @紫月 ）

確實用long long來存儲有點違背遊戲規則了......

只用int的話，倒也不是不能解決問題，只是這個時候我們可能要重溫一下CSAPP中的，判斷整數溢出的知識了。

我們可能都對書本上的那道練習題有深刻的印象：

加法由於阿貝爾群的關係，即使溢出，也依然遵從交換律，用做減法這種方式，是無法判斷加法運算過程中是否存在溢出的。

本題中需要判斷的運算是乘法。乘法會不會和加法一樣，也遵循相似的原則呢？

答案是否定的。

這一點其實相當的好玩——用減法，我們無法判斷出加法運算是否溢出，但用除法，我們就可以判斷乘法運算是否溢出。

CSAPP中給出的方法如下所示：

證明方法也是相當的嚴謹：

首先我們知道對於w位的x和y，x*y是可以用2w位二進位來表示的，我們將這2w位二進位拆為兩部分，高w位（用v來表示）和低w位（用u來表示），於是我們得到x*y=v*2w + u. u代表了代碼中p的二進位表示，根據無符號數轉換為有符號數的公式我們得到：u = p + p w?1 2w，於是我們可以將x * y = p + t * 2w. 根據溢出的定義，該乘法發生溢出當且僅當 t != 0。

其次，當x!=0的時候我們可以將p表示為p = x * q + r， |r| < |x|。於是我們有x * y = x * q + r + t * 2w。我們需要推導出t == 0的等價條件。當t = 0的時候，我們有x * y = x * q + r，而|r| < |x|，所以必有q=y；反過來,q=y的時候我們也可以推出t=0。也即是說t=0這個條件等價於q=y這個條件（前提是x不為0）。

q=p/x；

於是我們就得到了我們代碼裡面的判斷條件： !x || p/x == y

知道了除法可以判斷溢出，那麼我們的代碼就可以改改了。改進之後的Leetcode代碼如下所示：（經測試可以通過）

class Solution{public: int reverse(int x) { int temp=0; while(x!=0) { int check=temp; temp=10*temp+x%10; if(temp/10!=check) return 0; x/=10; } return temp; }};

推薦閱讀：