Prefix Substring LCS
(String/prefixsubstrlcs.hpp)

• View this file on GitHub
• Last update: 2024-01-18 04:47:59+09:00
• Include: #include "String/prefixsubstrlcs.hpp"

Depends on

• Binary Indexed Tree (DataStructure/bit.hpp)

Verified with

• Verify/LC_prefix_substring_lcs.test.cpp

Code

#pragma once
#include "DataStructure/bit.hpp"

template <typename T> struct PrefixSubstringLCS {
    using P = pair<int, int>;
    T s, t;
    int pos;
    vector<vector<vector<P>>> que;
    PrefixSubstringLCS() {
    }
    PrefixSubstringLCS(T &_s, T &_t)
        : s(_s), t(_t), pos(0), que(s.size(), vector(t.size(), vector<P>())) {
    }
    void add(int a, int b, int c) {
        if (a == 0 or c == 0) {
            pos++;
            return;
        }
        que[a - 1][c - 1].push_back({b, pos++});
    }
    vector<int> run() {
        vector<int> h(t.size()), ret(pos);
        iota(ALL(h), 0);
        rep(a, 0, s.size()) {
            int pre = -1;
            rep(c, 0, t.size()) {
                if (s[a] == t[c] or h[c] < pre)
                    swap(h[c], pre);
            }
            BIT<int> bit(t.size() + 1);
            rep(c, 0, t.size()) {
                if (h[c] != -1)
                    bit.add(h[c], 1);
                for (auto &[b, id] : que[a][c]) {
                    ret[id] = (c - b + 1) - (bit.all - bit.sum(b));
                }
            }
        }
        return ret;
    }
};

/**
 * @brief Prefix Substring LCS
 */

#line 2 "DataStructure/bit.hpp"

template<typename T>struct BIT{
    int n; T all=0; vector<T> val;
    BIT(int _n=0):n(_n),val(_n+10){}
    void clear(){val.assign(n+10,0); all=T();}
    void add(int i,T x){
        for(i++;i<=n;i+=(i&-i))val[i]=val[i]+x;
        all+=x;
    }
    T sum(int i){
        T res=0;
        for(;i;i-=(i&-i))res+=val[i];
        return res;
    }
    T sum(int L,int R){return sum(R)-sum(L);} // [L,R)

    int lower_bound(T x){
        int ret=0,len=1;
        while(2*len<=n)len<<=1;
        for(;len>=1;len>>=1){
            if(ret+len<=n and val[ret+len]<x){
                ret+=len;
                x-=val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */
#line 3 "String/prefixsubstrlcs.hpp"

template <typename T> struct PrefixSubstringLCS {
    using P = pair<int, int>;
    T s, t;
    int pos;
    vector<vector<vector<P>>> que;
    PrefixSubstringLCS() {
    }
    PrefixSubstringLCS(T &_s, T &_t)
        : s(_s), t(_t), pos(0), que(s.size(), vector(t.size(), vector<P>())) {
    }
    void add(int a, int b, int c) {
        if (a == 0 or c == 0) {
            pos++;
            return;
        }
        que[a - 1][c - 1].push_back({b, pos++});
    }
    vector<int> run() {
        vector<int> h(t.size()), ret(pos);
        iota(ALL(h), 0);
        rep(a, 0, s.size()) {
            int pre = -1;
            rep(c, 0, t.size()) {
                if (s[a] == t[c] or h[c] < pre)
                    swap(h[c], pre);
            }
            BIT<int> bit(t.size() + 1);
            rep(c, 0, t.size()) {
                if (h[c] != -1)
                    bit.add(h[c], 1);
                for (auto &[b, id] : que[a][c]) {
                    ret[id] = (c - b + 1) - (bit.all - bit.sum(b));
                }
            }
        }
        return ret;
    }
};

/**
 * @brief Prefix Substring LCS
 */

Back to top page