檢視上長回文子串的原始碼

'''上長回文子串'''（英語：Longest palindromic substring）是電腦科學中的問題，佇一字串內底走揣一个上長的連續的回文的囝串，比如講「banana」上長回文子串是「anana」。 上長回文子串並無一定是唯一的，比如講佇「abracadabra」中，無超過三字元的回文子串，但是有兩个回文字串長度攏是三：「 ada」和「aca」。 佇咧一寡應用中，咱求出全部的真大回文子串（無予其他回文串包括的回文子串）。

Glenn Manacher 佇一九七五年發現了一種線性時間演算法，會當佇列出予定字串內對任意位置開始的所有回文子串。並且，Apostolico , Breslauer & Galil 發現，仝款的演算法嘛會當佇任意位揣全部真大回文子串，並且時間複雜度是線性的。所以，𪜶提供了一種時間複雜度做線性的上長回文子串解法。另外咧，Jeuring ( 一千九百九十四 ) , Gusfield ( 一千九百九十七 ) 發現了對字尾樹仔的演算法。也存在已經知影的高效並列演算法。

上長回文子串演算法無應當佮上長回文子序列演算法相濫摻。

==定義==

===回文字串===

若一个長度為 $ n $ 的字攕 $ s $ 中間所有的字元依次為 $ s _ { 零 } , \ , s _ { 一 } , \ , s _ { 二 } \ , \ cdots \ , s _ { n 影一 } $ . 而且 $ s $ 滿足 $ \ forall i \ in \ left [零 , \ left \ lfloor { \ frac { n } { 二 } } \ right \ rfloor \ right] , \ ; s _ { i }=s _ { n-i 影一 } $ , 遐爾仔稱呼 $ s $ 為一个回文字串。

===上長回文子串===

彼若字攕 $ s $ 的一个回文子串 $ s _ { 一 } $ 是 $ s $ 所有回文子串中長度上長的，遐爾仔稱呼 $ s _ { 一 } $ 為 $ s $ 的上長回文子串。

==暴力回圈==

咧了解 Manacher 算法進前，咱先了解一下「笨」辦法，彼嘛就是暴力回箍，抑是講死算。

注意著乎每一个回文字串攏是以一个對稱點為中心左右對稱的，所以暴力運算的方式是阮迴箍逐字母作對稱點，然後佇每一个對稱點檢視所會當揣著的上大回文字串的長度，終其尾得著結果。

===偶長度回文字串的處理===

需要去注意著的一點，就是若單純共每一字元當做對稱點的話，干焦會當得著奇數長度的回文字串符。啊若回文字串可能是尪仔數長度的，比如講「cbaabd」中的「baab」，現此時對稱點是介於兩字元「a」中央的。若按呢，若直接共處理起來，可能會較麻煩，比如需要額外定義按怎表示字元中央的位置。

遮有一个巧妙的辦法，就是講佇字串中插一寡定位符，比如講「$」，比如講字捾「cbaabd」就會變做「$ c $ b $ a $ a $ b $ d $」。

現此時咱只需要按照奇長度字串的處理方式去處理這字串（揀逐改選著稱點干焦需要照次選取字元）， 上尾得著的回文字串「$ b $ a $ a $ b $」中，才閣共定位符「$」共用掉，咱就會當得著原始的尪仔長度字串「baab」了。

===虛擬碼===

===時間複雜度===

因為阮岫狀迴圈二改，外迴箍是 n 次，阮內迴圈平均落來是 n / 兩改，所以時間複雜度是 $ O ( n ^ { 二 } ) $。

==馬拉車演算法==

馬拉車演算法（英語：Manacher's algorithm）利用回文字串佮子回文字串中觀察著的一寡特點，以佇線性時間內揣出字串的上長回文子串。

首先咱來觀察一下回文字串可知，回文字串攏是對稱的。而且若一字回文字串的嘿稱點倒爿包含一个小的回文字串，遐爾仔對稱過去到正爿嘛必須會包含一个小的回文字串，比如講「dacabacad」這字貫內底，對稱點 b 倒爿有一个回文字串「aca」，正面嘛會對稱出一个回文字串「aca」。

===回文字串邊界的狀況討論===

啊咱觀察對稱點倒面出現的這个小回文字串，這字捾有三種狀況：

====狀況一====

若倒爿小回文字串的倒爿界佇大回文字串的倒爿界之內，遐爾正面對稱出的小回文字串嘛袂磕著大回文字串的正爿界。

比如講「d'''aca'''x'''aca'''d」這字攕，倒爿的「aca」無超過這个大回文字串的倒爿界，遐爾仔正面對稱出的「aca」嘛袂超過正爿界。

也就是講，佇這个情形下，正面這个小回文字串的長度佮對稱的小回文字串的長度相等，絕對'''袂超過'''這个大回文字串。

====狀況兩====

若倒爿小回文字串的倒爿界超過大回文字串的倒爿界，這个正面對稱出的小回文字串會正好觸著大回文字串的正爿界，但是袂超出。

譬如講觀察這个字串「'''dcbabcd'''xd'''cbabc'''e」。 倒爿的小回文字串的邊界超出用底線標出的大回文字串的倒爿界。對稱過來的正爿的小回文字串的邊界會拄好卡佇大回文字串的正爿界。這是大回文字串正爿界以外的後一个字母（此處是「e」）絕對毋是倒爿界的彼字母「d」的對稱，所以正爿的小回文字串延申到這个邊界了後嘛無法度閣繼續延申落去矣。

也就是講，佇這个情形下，正面這个小回文字串的正爿界佮大回文字串的正爿界相仝，遮爾這个小回文字串的長度嘛絕對'''袂超過'''這个大回文字串。

====狀況三====

若倒爿小回文字串的倒爿界拄好卡佇大回文字串的倒爿界上，遐爾正面對稱出的小回文字串有可能會繼續延續落去，超過大回文字串的正爿界。

譬如講觀察這个字串「abc'''dcbabcd'''xdcbabcdxdcb "，倒爿的小回文字串的倒爿界拄好卡佇大回文字串的倒爿界上，遐爾對稱過來的大回文字串是有可能繼續延申落去的。比如講佇這个比如講內底，正面以「a」為著對稱點的小回文字串一直向正延申到規个字串的結尾。

也就是講，佇這个情形下，正面這个小回文字串的正爿界至少佮大回文字串的正爿界相仝，而且有可能會延申。也就是講這个小回文字串的長度'''可能會超過'''這个大回文字串。

===總結===

阮考慮著倒爿的小回文字串的邊界佮大回文字串邊界的三種狀況，只有'''狀況三'''，也就是當好邊界佇仝一位的時陣，正爿的小回文字串的長度才有可能會超過大回文字串，若其他兩款情形，阮會當跳過袂去計算。

所以乎 Manacher 演算法佇先揣著一个回文字串了後，會當選擇性的跳過足濟字母，不需一一計算，佮暴力迴箍相比真大矣提升了演算法的效率。

===虛擬碼===

===時間複雜度===

假使阮逐改迴箍會當揣著的大回文字串的長度為 m，然後咱會當一直跳過計算，直接對該字攕的正爿界開始繼續迴圈。若字串的總長度為 n，阮干焦需要 n / m 改按呢的迴箍即可。確定 ｍ 的長度需要有內迴箍 ｍ 次。按呢咱來講，總時間複雜度是 ( n / m ) \ * m，也就是講 $ O ( n ) $。

==實現==

===Python===

注意，以下代碼並無完全照 Manacher 演算法執行，並無分情形討論，即無論是情況兩分之一 / 三中的佗一款情況攏想欲試向外繼續探測半徑敢會當延申。

雖然按呢會加幾改無路用的試驗，但是代碼會簡單呢。

另外需要注意的是，這段代碼並毋是回上長回文字串。

===C + +===



===Matlab===

===Java===

==參考資料==

[[分類: 待校正]]