palindrome

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

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

判斷迴文

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

bool palindrome(string s) { for (int i=0; i<s.size()/2; ++i) if (s[i] != s[s.size() - 1 - i]) return false; return true; } bool palindrome(char* s) { int length = strlen(s); for (int i=0; i<length/2; ++i) if (s[i] != s[length - 1 - i]) return false; return true; } bool palindrome(char* s) { for (int i=0, j=strlen(s)-1; i<j; ++i, --j) if (s[i] != s[j]) return false; return true; } bool palindrome(char* s) { char* t = s + strlen(s) - 1; for ( ; s < t; ++s, --t) if (*s != *t) return false; return true; }

UVa 10945 401 257 10716

演算法（dynamic programming）

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

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

// top-down char s[1000+1]; // 原序列 int dp[1000][1000]; // 儲存每個小問題的答案，初始化為-1 int p[1000][1000]; // 記錄每個小問題應當插入字母的地方 int f(int i, int j) { if (i == j) return 1; if (i > j) return 0; if (dp[i][j] != -1) return dp[i][j]; // 左右兩端字元相等，定能形成更長迴文，同時從兩端縮小問題範疇。 if (s[i] == s[j]) dp[i][j] = f(i+1, j-1) + 2, p[i][j] = 0; // 刪除左端字元比較好。 else if (f(i+1, j) > f(i, j-1)) dp[i][j] = f(i+1, j), p[i][j] = 1; // 刪除右端字元比較好。 else if (f(i+1, j) < f(i, j-1)) dp[i][j] = f(i, j-1), p[i][j] = 2; // 可以刪除其中一端的字元，都一樣好。 else /* if (f(i+1, j) == f(i, j-1)) */ dp[i][j] = f(i, j-1), p[i][j] = 3; return dp[i][j]; } void print(int i, int j) { if (i > j) return; // 當迴文長度為奇數，最中間的字母。 if (i == j) cout << s[i]; // 兩端字母一樣。 else if (p[i][j] == 0) cout << s[i], print(i+1, j-1), cout << s[i]; // 刪除左端字元。 else if (p[i][j] == 1) print(i+1, j); // 刪除右端字元。 else print(i, j-1); } void longest_palindromic_subsequence() { memset(dp, -1, sizeof(dp)); int N = strlen(s); cout << "最長迴文子序列的長度是" << f(0, N-1); cout << "最長迴文子序列是"; print(0, N-1); }

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了。小心處理字串長度是奇數的情況。

演算法（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。

char t[1001]; // 原字串 char s[1001 * 2]; // 穿插特殊字元之後的t int z[1001 * 2], L, R; // 源自Gusfield's algorithm // 由a往左、由b往右，對稱地作字元比對。 int extend(int a, int b, int N) { int i = 0; while (a-i>=0 && b+i<N && s[a-i] == s[b+i]) i++; return i; } void longest_palindromic_substring() { int N = strlen(t); // t穿插特殊字元，存放到s。 // （實際上不會這麼做，都是細算索引值。） memset(s, '.', N*2+1); for (int i=0; i<N; ++i) s[i*2+1] = t[i]; N = N*2+1; // s[N] = '\0'; // 可做可不做 // Manacher's algorithm z[0] = 1; L = R = 0; for (int i=1; i<N; ++i) { int ii = L - (i - L); // i的映射位置 int n = R + 1 - i; if (i > R) { z[i] = extend(i, i, N); L = i; R = i + z[i] - 1; } else if (z[ii] == n) { z[i] = n + extend(i-n, i+n, N); L = i; R = i + z[i] - 1; } else { z[i] = min(z[ii], n); } } // 尋找最長迴文子字串的長度。 int n = 0, p = 0; for (int i=0; i<N; ++i) if (z[i] > n) n = z[p = i]; // 記得去掉特殊字元。 cout << "最長迴文子字串的長度是" << (n-1) / 2; // 印出最長迴文子字串，記得別印特殊字元。 for (int i=p-z[p]+1; i<=p+z[p]-1; ++i) if (i & 1) cout << s[i]; } char t[1001]; char s[1001 * 2]; int z[1001 * 2]; void longest_palindromic_substring() { // t穿插特殊字元，存放到s。 int n = strlen(t); int N = n * 2 + 1; memset(s, '.', N); for (int i=0; i<n; ++i) s[i*2+1] = t[i]; // s[N] = '\0'; // z[0] = 1; // 無須使用，無須計算。 int L = 0, R = 0; for (int i=1; i<N; ++i) // 從z[1]開始 { z[i] = (R > i) ? min(z[2*L-i], R-i) : 1; while (i-z[i] >= 0 && i+z[i] < N && s[i-z[i]] == s[i+z[i]]) z[i]++; if (i+z[i] > R) L = i, R = i+z[i]; } // 尋找最長迴文子字串的長度 n = 0; int p = 0; for (int i=1; i<N; ++i) // 從z[1]開始 if (z[i] > n) n = z[p = i]; cout << "最長迴文子字串的長度是" << (n-1) / 2; } char s[1001]; // 原字串 int z0[1000], z1[1000]; // 偶數長度、奇數長度 void longest_palindromic_substring() { int N = strlen(s); memset(z0, 0, sizeof(z0)); memset(z1, 0, sizeof(z1)); // 奇數長度：中心i，右端i+z1[i]-1，長度2*z1[i]-1。 int L = 0, R = 0; for (int i=0; i<N; i++) if (i < R && z1[2*L-i] != R-i) z1[i] = min(z1[2*L-i], R-i); else { L = i; R = max(R, i); for (; R < N && 2*L >= R && s[2*L-R] == s[R]; R++); z1[i] = R-L; } // 偶數長度：中心i-1和i，右端i+z0[i]-1，長度2*z0[i]。 L = 0; R = 0; for (int i=0; i<N; i++) if (i < R && z0[2*L-i] != R-i) z0[i] = min(z0[2*L-i], R-i); else { L = i; R = max(R, i); for (; R < N && 2*L-1 >= R && s[2*L-1-R] == s[R]; R++); z0[i] = R-L; } // 尋找最長迴文子字串的長度 int n = 0, p = 0; for (int i=0; i<N; ++i) if (z0[i] * 2 > n) n = z0[p = i] * 2; else if (z1[i] * 2 - 1 > n) n = z1[p = i] * 2 - 1; cout << "最長迴文子字串的長度是" << n; }

dynamic programming O(N⁴)。

UVa 12473

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