test/aoj_alds1_10_c.test.cpp

View this file on GitHub
Last update: 2021-06-21 16:27:34+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C

Depends on

string/lcs_bit.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

#include "../string/lcs_bit.cpp"

int main() {
    int n;
    cin >> n;
    while(n--){
        string s, t;
        cin >> s >> t;
        cout << LCS_bit(s, t) << "\n";
    }
    return 0;
}

#line 1 "test/aoj_alds1_10_c.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

#line 1 "string/lcs_bit.cpp"
int LCS_bit(string &s, string &t){
    const int n = s.size(), m = t.size(), bit_sz = (m+63)>>6;
    vector<vector<ull>> p(256, vector<ull>(bit_sz, 0));
    for (int i = 0; i < m; ++i) {
        p[t[i]][i>>6] |= (1ULL << (i&63));
    }
    vector<ull> dp(bit_sz);
    for (int i = 0; i < m; ++i) {
        if(s[0] == t[i]) {
            dp[i>>6] |= (1ULL << (i&63));
            break;
        }
    }
    for (int i = 1; i < n; ++i) {
        ull shift = 1, sub = 0, tmp_sub = 0;
        for (int j = 0; j < bit_sz; ++j) {
            ull x = dp[j] | p[s[i]][j], y = (dp[j] << 1)|shift, z = x;
            shift = dp[j] >> 63;
            tmp_sub = z < sub;
            z -= sub;
            sub = tmp_sub;
            sub += z < y;
            z -= y;
            dp[j] = (z^x)&x;
        }
        dp[m>>6] &= (1LLU << (m&63))-1;
    }
    int ans = 0;
    for (int i = 0; i < bit_sz; ++i) {
        ans += __builtin_popcountll(dp[i]);
    }
    return ans;
}
#line 21 "test/aoj_alds1_10_c.test.cpp"

int main() {
    int n;
    cin >> n;
    while(n--){
        string s, t;
        cin >> s >> t;
        cout << LCS_bit(s, t) << "\n";
    }
    return 0;
}