2015-08-07

b478. 有限間距最長共同子序列

1. Problem
1. 1.1. 背景
2. 1.2. 題目描述
2. Sample Input
3. Sample Output
4. Solution

Problem

背景

有限間距最長共同子序列 (Gapped Longest Common Subsequence, 簡稱 GLCS) 是一種 LCS 的變形，而 LCS 想必早已成了經典題型。

回顧一下最長共同子序列 LCS 的解法，可以利用最簡單的 $O(NM)$ 動態規劃完成或者在特殊不重複情況下轉化成 LIS 在 $O(N \log N)$ 時間完成，轉換成 LIS 是有風險的，有機會退化成 $O(NM \log N)$。說不定還有比 $O(NM)$ 更快的算法去計算 LCS。

GLCS 的特點在於挑選子序列時，挑選到的相鄰字符位置之間最多有 $K$ 個字符不選。可強迫挑選出的相似序列盡可能是有意義的。

例如兩個字符串 $S, \; T$ 要求 GLCS，當 $K = 2$ 時：

$$S = \text{ACBDCAA} \\ T = \text{ADDBCDBAC}$$

則 ABCA 是一組合法的 $K = 2$ 時的 GLCS，挑選方案如下

    0123456789
S = ACBDCAA
    ^ ^ ^^
T = ADDBCDBAC
    ^  ^^  ^

若 $K = 1$ 時，由於字符串 $T$ 挑選 ABCA 時，前兩個字符之間的不選字符數為 2，不符合小於等於 $K$，則 ABCA 不能是 $K = 1$ 的合法 GLCS，而 CDA 是一組合法 $K = 1$ 時的 GLCS。

    0123456789
S = ACBDCAA
     ^ ^ ^
T = ADDBCDBAC
        ^^ ^

題目描述

給予兩個字符串 $S, \; T$ 以及限制間距 $K$，求出 GLCS 的長度為何。

Sample Input

1
2
3

2 ACBDCAA ADDBCDBAC
1 ACBDCAA ADDBCDBAC
0 ACBDCAA ADDBCDBAC

Sample Output

1
2
3

4
3
2

Solution

這一題是 Zerojudge a374. 5. 股票趨勢的簡化，股票趨勢那題要求的 $K$ 會隨著不同字符變動。如果固定 $K$，則可以利用單調隊列降到 $O(N^2)$。

GLCS 的遞迴公式如下：

$$T[i, j] := \left\{\begin{matrix} \textit{undefined} & A[i] \neq B[j] \\ max \;(T[a, b])+1 & A[i] = B[j], i - K - 1 \le a < i, j - K - 1 \le b < j \end{matrix}\right.$$

可以轉換成二維的 RMQ 問題，套用樹套樹結構可以單筆詢問 $O(\log^2 n)$ 完成。由於 DP 的掃描線性質，若用單調隊列單一詢問可以在 $O(1)$ 完成。比較裸的二維單調隊列求正方形窗口極值可以參考 BZOJ 1047 [HAOI2007] 理想的正方形。

對於二維的滑動窗口，則可以對每一列維護一個列的單調隊列，對於某一行掃描時，再維護一個行的單調隊列，往右移動窗口時，把移動到列的單調隊列的極值加入，並且把超出窗口的列的極值移除。
由上至下、由左而右掃描每一行上的元素，找到以此元素為正方形右下角的正方形區域最大最小值。

時間複雜度從 $O(N^2 + R \log^2 N)$ 降到 $O(N^2)$

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 2048;
template<typename WTYPE, bool FUNC(WTYPE, WTYPE)>
class MonoQueue {
public:
    deque< pair<int, WTYPE> > Q;
    int K;
    void setWindow(int K) {
        this->K = K;
    }
    inline void add(int idx, WTYPE val) {
        while (!Q.empty() && Q.front().first <= idx - K)
            Q.pop_front();
        while (!Q.empty() && FUNC(val, Q.back().second))
            Q.pop_back();
        Q.push_back({idx, val});
    }
    inline pair<int, WTYPE> top() {
        return Q.front();
    }
};
bool cmp(int a, int b) { return a >= b; }
char s1[MAXN], s2[MAXN];
int dp[MAXN][MAXN];
int main() {
    int N, M, K, val;
    while (scanf("%d %s %s", &K, s1+1, s2+1) == 3) {
        N = strlen(s1+1), M = strlen(s2+1), K++;
        int GLCS = 0;
        MonoQueue<int, cmp> mxC[MAXN];
                
        for (int i = 0; i < M; i++)
            mxC[i].setWindow(K);
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= M; j++)
                dp[i][j] = 0;
                
        for (int i = 0; i <= N; i++) {
            MonoQueue<int, cmp> mxR;
            mxR.setWindow(K);
            for (int j = 0; j <= M; j++) {
                    
                val = dp[i][j];
                mxC[j].add(i, val);
                mxR.add(j, mxC[j].top().second);
                
                if (s1[i+1] == s2[j+1])
                    dp[i+1][j+1] = mxR.top().second+1;
                GLCS = max(GLCS, val);
            }
        }
        printf("%d\n", GLCS);
    }
    return 0;
}

Morris' Blog