LCS(最長共通部分列)
(src/algorithm/LCS.hpp)

• View this file on GitHub
• Last update: 2022-10-21 15:10:55+09:00
• Include: #include "src/algorithm/LCS.hpp"

概要

LCS(std::vector<T>& a, std::vector<T>& b)

二つの列に対して最大共通部分列を求めます。

列$A$、$B$の共通部分列とは$A$、$B$両方の部分列である列を指します。部分列は元の列から0個以上の要素を省き残ったものを元の順序を保って並べたものです。

最大共通部分列は共通部分列の中で長さが最大のものです。

機能

• 関数に二つぶちこみましょう。std::stringにも対応しています。
• 共通部分列の中で長さが最大のものを一つ返します
  • 一般に最大共通部分列は一つに定まらないことに注意してください

計算量

• $O(NM)$ ( $N,\ M$ はそれぞれの列の長さ)

Verified with

• test/LCS.test.cpp

Code

#pragma once
#include <string>
#include <vector>
#include <algorithm>

namespace zawa::impl {

template <class T>
std::vector<T> lcs(const std::vector<T>& a, const std::vector<T>& b) {
    std::vector dp(a.size() + 1, std::vector(b.size() + 1, 0));
    for (std::size_t i = 0 ; i < a.size() ; i++) {
        for (std::size_t j = 0 ; j < b.size() ; j++) {
            if (a[i] == b[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            else {
                dp[i + 1][j + 1] = std::max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    std::vector<T> res;
    std::size_t i = a.size(), j = b.size();
    while (dp[i][j] > 0) {
        if (dp[i - 1][j] == dp[i][j]) {
            i--;
        }
        else if (dp[i][j - 1] == dp[i][j]) {
            j--;
        }
        else {
            i--;
            j--;
            res.emplace_back(a[i]);
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}

}

namespace zawa {

template <class T>
std::vector<T> lcs(const std::vector<T>& a, const std::vector<T>& b) {
    return impl::lcs(a, b);
}

std::string lcs(const std::string& a, const std::string& b) {
    std::vector<char> newa(a.begin(), a.end()), newb(b.begin(), b.end());
    std::vector<char> reschar = impl::lcs(newa, newb);
    return std::string(reschar.begin(), reschar.end());
}

} // namespace zawa

#line 2 "src/algorithm/LCS.hpp"
#include <string>
#include <vector>
#include <algorithm>

namespace zawa::impl {

template <class T>
std::vector<T> lcs(const std::vector<T>& a, const std::vector<T>& b) {
    std::vector dp(a.size() + 1, std::vector(b.size() + 1, 0));
    for (std::size_t i = 0 ; i < a.size() ; i++) {
        for (std::size_t j = 0 ; j < b.size() ; j++) {
            if (a[i] == b[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            else {
                dp[i + 1][j + 1] = std::max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    std::vector<T> res;
    std::size_t i = a.size(), j = b.size();
    while (dp[i][j] > 0) {
        if (dp[i - 1][j] == dp[i][j]) {
            i--;
        }
        else if (dp[i][j - 1] == dp[i][j]) {
            j--;
        }
        else {
            i--;
            j--;
            res.emplace_back(a[i]);
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}

}

namespace zawa {

template <class T>
std::vector<T> lcs(const std::vector<T>& a, const std::vector<T>& b) {
    return impl::lcs(a, b);
}

std::string lcs(const std::string& a, const std::string& b) {
    std::vector<char> newa(a.begin(), a.end()), newb(b.begin(), b.end());
    std::vector<char> reschar = impl::lcs(newa, newb);
    return std::string(reschar.begin(), reschar.end());
}

} // namespace zawa

Back to top page