F - Operate K Editorial by MMNMM

より高速な解法

この問題を \(O(|S|+|T|+K ^ 2)\) 時間で解く方法について解説します（実装例では、時間計算量を \(O(|S|+|T|+K ^ 2\log(|S|+|T|))\) としています）。

参考：入力長に対して線形時間 + 編集距離に対して二乗時間で LCS を求めるよ - えびちゃんの日記

\(S,T\) の編集距離は、次のような重み付き有向グラフでの最短路問題と考えることができます。

\(i=0,1,2,\ldots,|S|\) と \(j=0,1,2,\ldots,|T|\) の組 \((i,j)\) を頂点とし、以下の辺

  • \((i,j)\rightarrow(i+1,j)\) に、重み \(1\) の辺
  • \((i,j)\rightarrow(i,j+1)\) に、重み \(1\) の辺
  • \((i,j)\rightarrow(i+1,j+1)\) に、\(S _ {i+1}=T _ {i+1}\) ならば重み \(0\) 、そうでなければ重み \(1\) の辺

からなるグラフを考える。 \((0,0)\) から \((|S|,|T|)\) への最短路長が \(S,T\) の編集距離と等しい。

このグラフ上で \((0,0)\) からの距離が \(d\) 以下であるような頂点の集合 \(S _ d\) について考えます（\(01\)-BFS（もしくはダイクストラ法）を行うことを考えて、距離が増えるステップごとにそれまでに訪れた頂点の集合を見ていると思うことができます）。

\((|S|,|T|)\in S _ K\) かどうかを判定することで、この問題を解くことができます。

以下では、文字列 \(X\) の \(i\) 文字目以降からなる接尾辞を \(X\lbrack i\ldots\rbrack\) で表すこととし、文字列 \(X,Y\) の最長共通接頭辞の長さを \(\operatorname{LCP}(X,Y)\) と書くこととします。

任意の非負整数 \(d\) について、\(S _ d\) はある長さ \(|S|+|T|+1\) の列 \((u _ {-|S|},u _ {-|S|+1},\ldots,u _ {|T|})\) によって次の形で表せることを示します。

\[S _ d=\bigcup _ {k=-|S|} ^ {|T|}\lbrace(i,j)\mid 0\leq i\leq u _ k\wedge0\leq j\wedge i+k=j\rbrace\]

証明

帰納法で示します。 \(S _ 0\) は \(\lbrace (0,0),(1,1),\ldots,(\operatorname{LCP}(S,T),\operatorname{LCP}(S,T))\rbrace\) となるので、成り立ちます。

\(S _ d\) について成り立っていると仮定します。 このとき、\(S _ {d+1}\) のうち \((i,i+k)\) の形で書けるものは、以下のいずれかです。

  1. \((i ^ \prime,i ^ \prime+k)\in S _ d\) からの距離が \(1\) 以下
  2. \((i ^ \prime,i ^ \prime+k+1)\in S _ d\) からの距離が \(1\) 以下
  3. \((i ^ \prime,i ^ \prime+k-1)\in S _ d\) からの距離が \(1\) 以下

\(1.\) について、仮定よりある \(u ^ \prime _ k\) が存在して \(i ^ \prime\leq u ^ \prime _ k\iff(i ^ \prime,i ^ \prime+k)\in S _ d\) です。 これらからの距離が \(1\) 以下であるような \((i,i+k)\) の形で書ける頂点は、これらそのものであるか、辺 \((u ^ \prime _ k,u ^ \prime _ k+k)\rightarrow(u ^ \prime _ k+1,u ^ \prime _ k+k+1)\) を使ったのち \(0\) 回以上コスト \(0\) の辺を進んだものです。

よって、\(1.\) を満たすものは \((i,i+k)\ (0\leq i\leq u ^ \prime _ k+1+\operatorname{LCP}(S\lbrack u ^ \prime _ k+1\ldots\rbrack,T\lbrack u ^ \prime _ k+k+1\ldots\rbrack),0\leq j))\) の形で表すことができます。

\(2.\) および \(3.\) も同様の議論を行うことで、\(u _ k=\max\lbrace u ^ \prime _ k+1+\operatorname{LCP}(S\lbrack u ^ \prime _ k+1\ldots\rbrack,T\lbrack u ^ \prime _ k+k+1\ldots\rbrack),u ^ \prime _ {k+1}+1+\operatorname{LCP}(S\lbrack u ^ \prime _ {k+1}+1\ldots\rbrack,T\lbrack u ^ \prime _ {k+1}+k+1\ldots\rbrack,u ^ \prime _ {k-1}+\operatorname{LCP}(S\lbrack u ^ \prime _ {k-1}\ldots\rbrack,T\lbrack u ^ \prime _ {k-1}+k\ldots\rbrack\rbrace\) とできることがわかります。\(\square\)

ここで、\(i+k=j\) なる \((i,j)\) へ到達するためには重み \(1\) の辺を \(|d|\) 回以上通る必要があることから、\(S _ K\) までの計算では \(-K\leq k\leq K\) に対応する長さ \(2K+1\) の列を管理すればよいことがわかります。

あとは、\(S _ 0\) に対応する列 \((-1,-1,\ldots,-1,0,-1\ldots,-1,-1)\) からはじめ、上の証明に従って列を更新すればよいです。

更新のためには \(\operatorname{LCP}(S\lbrack i\ldots\rbrack,T\lbrack j\ldots\rbrack)\) を高速に求める必要がありますが、これは適当な文字列に対する Suffix Array と LCP Array を求めておき、適切な列に対する区間最小値クエリに答えることで計算することができます。

区間最小値クエリを処理する際にセグメント木を用いると全体の時間計算量を \(O(|S|+|T|+K ^ 2\log(|S|+|T|))\) などに、いわゆる線形 RMQ を用いると \(O(|S|+|T|+K ^ 2)\) などとすることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <atcoder/string>
#include <atcoder/segtree>

int main() {
    using namespace std;
    unsigned K;
    string S, T;
    cin >> K >> S >> T;

    const auto N{size(S)}, M{size(T)};

    // 長さの差が大きい場合、No
    if (min(N, M) + K < max(N, M)) {
        cout << "No" << endl;
        return 0;
    }

    // S, T の suffix に対する LCP を高速に求める
    const auto lcp_query{
        [N, M, lcp_info{
            // セグメント木と、LCP Array における suffix の位置の情報を前計算しておく
            [N, M, &S, &T] {
                // 連結して Suffix Array, LCP Array を求める
                string U{S + '.' + T};
                const auto sa{atcoder::suffix_array(U)};
                const auto lcp{atcoder::lcp_array(U, sa)};

                // LCP Array の区間最小値を求めるセグメント木
                atcoder::segtree<int, [](const auto a, const auto b) { return min(a, b); }, [] { return numeric_limits<int>::max(); }> sgt(lcp);

                // Suffix Array を見てインデックスを計算する
                vector<unsigned> s_idx(N), t_idx(M);
                for (unsigned i{}; i < N + 1 + M; ++i) {
                    if (sa[i] < N)
                        s_idx[sa[i]] = i;
                    if (sa[i] > N)
                        t_idx[sa[i] - N - 1] = i;
                }

                return make_tuple(sgt, s_idx, t_idx);
            }()
        }](unsigned s, unsigned t) {
            if (s >= N || t >= M)
                return 0;
            const auto& [segment_tree, s_index, t_index]{lcp_info};
            return segment_tree.prod(min(s_index[s], t_index[t]), max(s_index[s], t_index[t]));
        }
    };

    // dp[k] := (i, i + k) の形の現在到達している頂点のうち、最大の i の値
    vector<unsigned> _dp(2 * K + 1), _prev(2 * K + 1);
    const auto dp{begin(_dp) + K}, prev{begin(_prev) + K};

    // 距離 0 では (LCP(S, T), LCP(S, T)) まで到達できる
    dp[0] = lcp_query(0, 0);

    const auto chmax{
        [](auto&& a, const auto& b) {
            if (a < b)
                a = b;
        }
    };

    for (unsigned i{}; i < K; ++i) {
        ranges::copy(_dp, begin(_prev));
        // 配る DP で計算
        for (auto d{-static_cast<ptrdiff_t>(i)}; d <= i; ++d) {
            chmax(dp[d], prev[d] + 1 + lcp_query(prev[d] + 1, prev[d] + d + 1));
            chmax(dp[d + 1], prev[d] + lcp_query(prev[d], prev[d] + d + 1));
            chmax(dp[d - 1], prev[d] + 1 + lcp_query(prev[d] + 1, prev[d] + d));
        }
        // (|S|, |T|) に到達できれば Yes
        if (dp[static_cast<ptrdiff_t>(size(T)) - size(S)] >= size(S)) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    // 到達できなければ No
    cout << "No" << endl;
    return 0;
}

posted:
last update: