test/aoj/alds1/alds1_10_c.test.cpp

View this file on GitHub
Last update: 2024-05-04 18:06:16+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

Depends on

Longest Common Subsequence (lib/dp/LCS.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/dp/LCS.hpp"

int main(){
    int q; cin >> q;
    while(q--){
        string s, t; cin >> s >> t;
        cout << (int) LCS(s, t).size() << "\n";
    }
}

#line 1 "test/aoj/alds1/alds1_10_c.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/dp/LCS.hpp"

/**
 * @brief Longest Common Subsequence
 * @docs docs/dp/LCS.md
 */

string LCS(const string &s, const string &t){
    int n = s.size(), m = t.size();
    vector<vector<int>> memo(n + 1, vector<int>(m + 1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i] == t[j]){
                memo[i + 1][j + 1] = memo[i][j] + 1;
            } else{
                memo[i + 1][j + 1] = max(memo[i][j + 1], memo[i + 1][j]);
            }
        }
    }

    // 復元
    string res = "";
    int i = n - 1, j = m - 1;
    while(0 <= i && 0 <= j){
        if(s[i] == t[j]){
            res += s[i];
            i--; j--;
        } else if(memo[i + 1][j + 1] == memo[i][j + 1]){
            i--;
        } else if(memo[i + 1][j + 1] == memo[i + 1][j]){
            j--;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}
#line 6 "test/aoj/alds1/alds1_10_c.test.cpp"

int main(){
    int q; cin >> q;
    while(q--){
        string s, t; cin >> s >> t;
        cout << (int) LCS(s, t).size() << "\n";
    }
}