CF 822 E - Liar

問題

Problem - E - Codeforces

問題概要

長さの文字列と長さの文字列が与えられる。をいくつかの部分文字列に分解して、その中から任意の個数を選んで順序を崩さないように結合させる。その結合させた文字列をと一致させるために、できるだけ結合の数減らしたい。個以下の文字列で実現できるかを判定せよ。

• 
• はアルファベット小文字
• 

アイデア

計算量をとりあえず気にしないのであれば、とりあえずdp[i][j] = sのi文字目まで使った、tのj文字目まで使った状況での分割回数のminを持つとdp[n][m]<=xかどうかで判定ができるが、明らかに間に合わない。

ここで、分割回数の上限が小さいことに着目すると、次のようなdpも考えられる：dp[i][j] := sのi文字目まで使った、既に連結した文字列がj個の時、tの何文字目までを作れるかのmax。このようにすると状態数はになる。そして、遷移がどうなるのかというのを考えると、1,2,3, ... 文字を採用するというのを全部試すというのは結局ムリだが、i文字目からスタートする部分文字列を採用する時場合は、最適なのは取れる限りまで取る(中途半端に切るのは無駄)ということしか考える必要がないので、各状態において遷移は「i文字目からスタートするものを採用する/しない」の2つしかいらないことになる。

sのi文字目からと、tのdp[i][j]文字目からのLCPはSuffixArrayにsとtを結合させたものを入れておいて、RMQを使うことで高速に処理することが出来るので、DPの遷移はになる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct SuffixArray{
    const string &s;

    int n;
    vector<int> sa, rank;
    vector<int> lcp;

    void construct_sa(){
        sa.resize(n+1);
        rank.resize(n+1);
        // 1文字でのランク
        rep(i,n+1){
            sa[i] = i;
            rank[i] = (i<n)?s[i]:-1;
        }
        vector<int> tmp(n+1,0);
        for(int k=1; k<=n; k*=2){
            auto comp = [&](const int i, const int j){
                if(rank[i] != rank[j]) return rank[i] < rank[j];
                int ri = (i+k<=n)?rank[i+k]:-1;
                int rj = (j+k<=n)?rank[j+k]:-1;
                return ri < rj;
            };
            sort(all(sa), comp);
            tmp[sa[0]] = 0;
            for(int i=1; i<=n; ++i){
                tmp[sa[i]] = tmp[sa[i-1]];
                if(comp(sa[i-1], sa[i])) ++tmp[sa[i]];
            }
            swap(tmp, rank);
        }
    }

    SuffixArray(const string &str) : s(str){
        n = s.size();
        construct_sa();
    }

    // lcp配列が欲しかったら個別に呼ぶ
    void construct_lcp(){
        lcp.resize(n+1);

        int h = 0;
        lcp[0] = 0;
        rep(i,n){
            int j = sa[rank[i]-1];

            // hを先頭のぶん減らし、後ろが一致しているまで増やす
            if(h>0) --h;
            for(; j+h<n && i+h<n; ++h){
                if(s[j+h] != s[i+h]) break;
            }

            lcp[rank[i]-1] = h;
        }
    }

    int getRank(const string &t) const {
        int m = t.size();
        int l = 0, r = n+1;
        while(r-l>1){
            int mid = (l+r)/2;
            if(s.compare(sa[mid], m, t) < 0) l = mid;
            else r = mid;
        }
        return r;
    }
};

const ll INF = LLONG_MAX/3;

struct SegTree{
    int n; vector<ll> dat;
    //初期化
    SegTree(int _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<ll>(2*n-1,INF);
    }
    //k番目(0-indexed)の値をaに変更
    void update(int k, ll a){
        k+=n-1;
        dat[k]=a;
        //更新
        while(k>0){
            k=(k-1)/2;
            dat[k]=min(dat[2*k+1],dat[2*k+2]);
        }
    }
    //内部的に投げられるクエリ
    ll _query(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return INF;

        if(a<=l && r<=b) return dat[k];

        ll vl=_query(a,b,2*k+1,l,(l+r)/2);
        ll vr=_query(a,b,2*k+2,(l+r)/2,r);
        return min(vl,vr);
    }
    //[a,b)
    ll query(int a, int b){
        return _query(a,b,0,0,n);
    }
};

const int N = 100010, X = 32;
int dp[N][X];

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int n,m,x;
    string s,t;
    cin >>n >>s >>m >>t >>x;

    string C = s+'#'+t;
    SuffixArray sa(C);
    sa.construct_lcp();

    vector<int> l = sa.lcp;
    int L = l.size();
    SegTree st(L);
    rep(i,n+m+1) st.update(i, l[i]);

    rep(i,n)rep(j,x+1){
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
        if(j<x){
            int RI = sa.rank[i], RJ = sa.rank[n+1+dp[i][j]];
            // printf(" RI RJ %d %d\n",RI,RJ);
            // printf("index: %d %d,  lcp %d\n",i,n+1+dp[i][j],add);
            if(RI>RJ) swap(RI,RJ);
            int add = st.query(RI,RJ);
            int ni = i + add;
            dp[ni][j+1] = max(dp[ni][j+1], dp[i][j]+add);
        }
    }

    string ans = "NO";
    rep(i,x+1)if(dp[n][i]==m) ans = "YES";
    cout << ans << endl;
    return 0;
}