palindrome

palindrome

「迴文」。中文當中是指倒正著念和反著念都相同的句子,前後對稱,例如「上海自來水來自海上」。英文當中是指正著看和反著看都相同的單字,例如「madam」。

不是迴文的例子:「aabb」、「abcabc」。下圖也非迴文,儘管它非常對稱:

判斷迴文

左端右端同步往中央移動,逐一比對字元。如果字串長度為奇數,那麼不必檢查中央字元。

UVa 10945 401 257 10716

longest palindromic subsequence

演算法(dynamic programming)

削減兩端元素,判斷是否對稱,遞迴縮小問題。

找出一個最長迴文子序列,時間複雜度O(N²)。

UVa 11151 11404 10453 10617 10739 11584 689

LPS問題化作LCS問題

原本序列、反轉序列,兩者的LCS長度即是LPS長度,兩者的所有LCS涵蓋了所有LPS。

        s  = 1 5 2 4 3 3 2 4 5 1
reverse(s) = 1 5 4 2 3 3 4 2 5 1
       LCS = 1 5   4 3 3   4 5 1
       LPS = 1 5   4 3 3   4 5 1

可能其中一些LCS不是LPS。左右不對稱。

       LCS = 1 5 2   3 3   4 5 1   ✘

解決方法:LCS只求左半段,自行回文得到右半段,就保證是LPS了。小心處理字串長度是奇數的情況。

longest palindromic substring

演算法(Manacher's algorithm)

運用了Gusfield's algorithm的概念。時間複雜度O(N)。

建立一個表格z()。以s[i]為中心的最長迴文,從中心到外端的長度,儲存至z(i)。s[i ... i-z(i)+1] = s[i ... i+z(i)-1]呈鏡面對稱。

這種方式無法記錄偶數長度的迴文。解決辦法是:在每個字元中間,插入同樣一個並且沒出現過的字元,如此就只剩下奇數長度的迴文了,而且也能記錄原先偶數長度的迴文。

  |                    10  12  14  16
  | 0 1 2 3 4 5 6 7 8 9  11  13  15
--+-----------------------------------
s | a b a a b a a b
s'| . a . b . a . a . b . a . a . b .
z | 1 2 1 4 1 2 7 2 1 8 1 2 5 2 1 2 1

z(0)=1:.,由中心可以左右延伸長度1。
z(1)=2:.a.,由中心可以左右延伸長度2。
z(2)=1:.,由中心可以左右延伸長度1。
z(3)=4:.a.b.a.,由中心可以左右延伸長度4。

z(0)是特例,等於1。由z(1)開始算。

計算z(i),是運用已經算好的z(j),j < i。也就是指某一段已經算好的s[j ... j-z(j)+1] = s[j ... j+z(j)-1]。首先找出有覆蓋到s[i]的s[j ... j+z(j)-1]是那一段,而且j+z(j)-1越右邊越好。

一、如果找不到可以覆蓋s[i]的s[j ... j+z(j)-1],表示已經算好的部份都派不上用場。從s[i+1]與s[i-1]開始比對,逐字比下去。

二、如果找到可以覆蓋s[i]的s[j ... j+z(j)-1],表示s[i]也會出現在s[j ... j-z(j)+1]之中,把i鏡射到對應的位置i'。接著運用z(i'),也就是指s[i' ... i'-z(i')+1] = s[i' ... i'+z(i')-1]。

二之一、如果s[i ... i+z(i')-1]短少於s[j ... j+z(j)-1]的右端,那就可以直接算出z(i)的答案,就是z(i')。

二之二、如果s[i ... i+z(i')-1]剛好貼齊s[j ... j+z(j)-1]的右端,那就必須檢查未確定的部分,直接從s[i+z(i')]與s[i-z(i')]繼續比對,逐字比下去。

二之三、如果s[i ... i+z(i')-1]突出了s[j ... j+z(j)-1]的右端,根據z(j)可知s[j-z(j)]與s[j+z(j)]一定是不同字元,根據z(i')可知s[j-z(j)]與其鏡射位置是相同字元。對於i來說,s[j+z(j)]與其鏡射位置就會是不同字元,不可能形成更長的迴文,因此可以直接算出z(i)的答案,就是j+z(j)-i。

longest common palindromic subsequence

dynamic programming O(N⁴)。

UVa 12473

longest common palindromic substring

Manacher's algorithm + sufffix tree O(N)。