前置技能

• DP
• LIS

原問題

給一序列 s，求所有 s 的子序列中，滿足「迴文」條件的最長子字列長度。

觀察

這裡略過一般迴文 DP 的 n^2 解法。

對於任何一組長度 n 的迴文，滿足以下條件：

s[0] == s[n-1]
s[1] == s[n-2]
s[2] == s[n-3]
...

由此性質，可發現迴文子序列由原序列中的 matching 組成；
即滿足 s[i] == s[j] 的 matching (i, j)

例如序列 acabca

其具有 matching

• (0, 2)
• (0, 5)
• (1, 4)

則其最長迴文子序列，基於迴文定義，必由以上 matching 所組成。
兩個 matching 能出現在同一子序列，並維持迴文定義，
則此兩 matching (i, j), (p, q) 必滿足以下條件：

(i > p && q < j) || (p > i && j < q)

如此它們會呈現 ipqj 或 pijq 的長相，又 s[i] == s[j] 且 s[p] == s[q]
故會長得像 abba 或 baab 的樣子。
而迴文子序列中任兩 matching 均滿足此條件。

於是題目被轉成對所有這樣的 matching 找出最長遞增子序列，
兩 matching (i, j), (p, q) 遞增條件是 (i>p && q<j) || (p>i && j<q)

解法

對二維以上的東西做 LIS 會使 n lg n 的 LIS 做法，因無法保證哪個是最佳結尾而無法使用。

不過剛好只有二維的時候，可以透過排序使其中一維維持不遞減，
變成只看另一維的 LIS。

注意由於其中一維只是不遞減，該維相同時需將另一維以想要的順序倒序排序，以讓它們必無法相接。

例如 (0, 2), (0, 5), (0, 4) 這三者依第一維排序時順序相同，
迴文需要第一維嚴格遞增、第二維嚴格遞減，因此第一維相同時，
將第二維依小排到大，變成 (0, 2), (0, 4), (0, 5)
由於 2 不可接 4, 5、4 不可接 5，如此避免了它們之間因不看第一維而互接。

最後得到的 LIS 長度乘以 2，如果最末尾數對 (i, j) 其中 i, j 並不是連續的，
則表示它們之間有其它字母存在，單一字母必為迴文，因此答案需要 + 1，
如此即為最長迴文子序列長度。

LIS 具有 m lg m 的解法，事前需 m lg m 的排序。
m 為 matching 數，而 matching 數最糟是 n^2
於是得出了一個最糟 n^2 lg n^2 的解法，比原本的解法更糟。

優化

我們可以用線性的時間，將序列掃過，把相同的字母存成一條陣列。

之後我們再次掃過原序列，此順序相當於第一維不遞減；
用一陣列存每個字母現在是第幾個，如此便不需要進行排序，
即可以 m 的時間複雜度依序得到所有合法 matching。

對所有第一維相同的 matching，如上所述希望順序由小到大，
以避免誤接的情況。這點在建表時已經完成。

由於此順序性，可保證其在 LIS n lg n 做法中，
其位置同樣具有順序性。

LIS 複雜度中的 log 的由來本是，
在 [i] = k 代表長度 i 的遞增子序列中，結尾 k 最佳，
且其具有若 i 遞減，則 k 會遞增的方向性。
越大的 k 越接不長，所以長度 i 越長，k 就會越小。

因此我們可對其 binary search 找到所有可以接上我們目前 matching，
也就是 k 比我們目前 matching 第二維大的中，最小的（也是最長的）一個。

由於第一維相同的 matching 的順序性，我們第二維只會越來越大，
能接的 k 也只能越來越大，不會越來越小，因此長度 i 只會不變或者遞減，絕對不會遞增。

故我們可以捨棄二分搜尋，對每個 matching 從上一個的位置往更小的 i 去找對應的 k。

如此，對於我們掃過序列中 n 個字母，每個字母最糟有 n 個 matching，這裡 n*n；
對於這 n 個 matching，尋找可串接的最長子序列時，要嘛直接找到 (1次) 要嘛往下找，
往下找對這 n 個 matching 總共最多只出現 n 次，就會到底，
所以總和只有 2n 次，這裡 n(個字母) * 2n(這 n 個 matching 總和最多只掃 2n 次)。

得到一個 n * n + n * 2n => O(n^2) 的方法。
但比起之前一定得做滿 n^2 的方法，此方法受 matching 數和 LIS 長度所影響，
在大多數情形是比 n^2 要來得小的。

以下附上參考 code:

// ary[i][j] 存字元 i 第 j 個出現位置為何
int ary[128][N];
// an[i] 存字元 i 共出現幾次。ary 使用 std::vector<int> 時不需要它。
int an[128];
// pa[i] 存字元 i 目前出現第幾次。快速反查目前掃到第幾個字元 i 時使用。
int pa[128];
// dp[i] = k 表示長度 i+1 的遞增子序列，最佳（可拓展性最大）尾巴是 k
int dp[N];
// 目標子序列
char s[N];

// input 和初始化
scanf("%s", &s);
for (i='A'; i<='Z'; i++)
{
    an[i] = 0;
    pa[i] = 0;
}

// 對 ary 建表，存所有字元出現位置，以產生數對使用
for (len=0; s[len]; len++)
{
    ary[s[len]][an[s[len]]++] = len;
}

// 開始 DP
for (i=0, d=-1, ans=0; i<len; i++)
{
    c = s[i];
    // k 為可串接的最長尾巴的長度，原本做法中透過 binary search 取得
    // 此長度對所有第一維是 s[i] 的 matching 中不遞增，所以乾脆不 binary search 硬掃
    k = d;
    p = ary[c][pa[c]];
    // 撈出所有第一維是 s[i] 的數對；pa[ s[i] ] 會是 s[i] 是相同字元中第幾個
    for (j=pa[c]+1; j<an[c]; j++)
    {
        t = ary[c][j];
        // 重點: 不初始化 k，從上個 matching 的位置直接往下找，才能把這層迴圈均攤成 O(1)
        for (; k>=0&&t>=dp[k]; k--);
        dp[k+1] = t;
        // 看看最大長度 d 是否有上升
        if (k+1 > d)
        {
            d = k+1;
        }
        // 以當前 matching 為最後一個 matching 時的迴文子序列長度
        // matching 數乘以 2 (一個 matching 提供兩個字元)
        // 最後看位置 p 和 t 是否連續，不連續表示中間有其它字元，長度 + 1
        a = ((k+2)<<1)+(p+1<t);
        if (a > ans)
        {
            ans = a;
        }
    }
    // 記得讓 pa[ s[i] ] 前進
    ++pa[c];
}

// ans 即為所求
printf("%d\n", ans);