Template. Longest Common Subsequence

Dynamic Programming

時間複雜度：$O(N^2)$

#define maxn 1000
int lcs(string a, string b) {
    int dp[maxn + 1][maxn + 1];
    dp[0][0] = dp[1][0] = dp[0][1] = 0;
    for (int i = 1; i <= a.length(); i++)
        for (int j = 1; j <= b.length(); j++)
            if (a[i - 1] == b[j - 1])
                lis[i][j] = lis[i - 1][j - 1] + 1;
            else
                lis[i][j] = max(lis[i - 1][j], lis[i][j - 1]);
    return lis[a.length()][b.length()];
}

Greedy

首先用 $O(N)$ 的方式先將LCS問題轉成LIS，再用Greedy方式算出LCS。
參考資料：演算法筆記。
時間複雜度：$O(N log N)$

int lcs(string a, string b) {
    if (a.length() < b.length())
        swap(a, b);
    vector<int> tmp[256];
    for (int i = 0; i < a.length(); i++)
        tmp[a[i]].push_back(i);
    vector<int> lis;
    lis.push_back(-1);
    for (int i = 0; i < b.length(); i++) {
        int now = b[i];
        for (int i = tmp[now].size() - 1; i >= 0; i--)
            if (tmp[now][i] > lis.back())
                lis.push_back(tmp[now][i]);
            else
                *lower_bound(lis.begin(), lis.end(), tmp[now][i]) = tmp[now][i];
    }
    return lis.size() - 1;
}