Question

仁智怀德圣虞唐，贞志笃终誓穹苍，　　　　　

钦所感想妄淫荒，心忧增慕怀惨伤。《璇机图》

Palindrome

“迴文”在中文当中是指倒正著念和反著念都相同的句子，前后对称，例如“上海自来水来自海上”。在英文当中是指正著看和反著看都相同的单字，例如“madam”。

另外也举些不是迴文的例子：“aabb”、“abcabc”。下图也非迴文，儘管它非常对称：

要检查一个单字是否是迴文很简单：

Longest Palindromic Subsequence

Longest Palindromic Subsequence

是迴文而且是最长的子序列，可能有许多个。

  s = 1 5 2 4 3 3 2 4 5 1
LPS = 1 5   4 3 3   4 5 1

演算法（Dynamic Programming）

利用迴文的特性，从字串的左右两端判断其是否对称，来缩小问题范畴。找出一个最长迴文子序列的时间複杂度是 O(N^2)。

UVa 11151 11404 10453 10617 10739 11584 689

演算法（Longest Common Subsequence）

原本字串与反转字串，两者的 LCS 长度即是 LPS 长度，两者的所有 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 2   3 3   4 5 1

s 和 reverse(s) 的 LCS 不一定刚好就是迴文，会有左右不对称的问题。

LCS 只求前半段，再自行回文得到后半段，就得到 LPS 了。

【待补证明】

Longest Palindromic Substring

演算法（Manacher's Algorithm）

运用了 Gusfield's Algorithm 的概念。时间複杂度为 O(N)。

定义一个函数 z()，z(i) 是指以 s[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()，是由左往右算。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^4)。

http://arxiv.org/pdf/1110.5296v1.pdf

UVa 12473

Longest Common Palindromic Substring

Manacher's Algorithm + Sufffix Tree O(N)。

https://www.quora.com/What-is-the-best-way-to-find-the-longest-common-palindromic-substring-between-2-strings