最長共通部分文字列

string/longest_common_substring.hpp · GitHub で見る

共通ページ

2 つの文字列の最長共通部分文字列を 1 つ求めます。選ぶ文字は連続している必要があります。飛び飛びの文字も選べる最長共通部分列とは異なります。

#include "lib/string/longest_common_substring.hpp"
#include <string>

std::string s = "ABABC", t = "BABCA";
auto result = longest_common_substring(s, t);
int i = result.s_pos;   // 1
int j = result.t_pos;   // 0
int len = result.length; // 4
auto common = s.substr(i, len); // "BABC"
auto [a, b, length] = longest_common_substring(s, t);

longest_common_substring(s,t) は std::string_view を受け取り、LongestCommonSubstringResult を返します。std::string・文字列リテラル・std::string_view を渡せます。返す s_pos・t_pos はそれぞれの入力での 0-indexed の開始位置で、length は長さです。

半開区間 s[s_pos,s_pos+length) と t[t_pos,t_pos+length) が一致します。解が複数ある場合はそのうち 1 つを返し、開始位置の優先順は保証しません。一方が空、または共通する文字がない場合は全フィールドが 0 です。

入力を変更せず、結果は入力を参照しません。NUL を含む全 256 種類のバイトに対応します。埋め込み NUL は長さを指定した string_view または string で渡してください。添字・長さはバイト単位なので、UTF-8 の文字境界は扱いません。入力の長さの合計は INT_MAX-1 以下としてください。

短い一致部分から候補を絞って厳密に比較し、作業量が増える場合は SA-IS と Kasai の方法へ切り替えます。全てのバイトで一致を確認し、ハッシュ値の一致だけで答えを確定しません。

入力長をそれぞれ \(n,m\) とすると、時間・追加空間はともに \(O(n+m)\) です。

依存ライブラリ

• 共通接頭辞・接尾辞の比較
• Common Substring Seed Search
• Suffix Array Core

検証コード

• test/longest_common_substring.test.cpp

コード

#ifndef LONGEST_COMMON_SUBSTRING_HPP
#define LONGEST_COMMON_SUBSTRING_HPP

#include "../components/sequence_compare.hpp"
#include "../components/suffix_array.hpp"
#include "../components/substring_seed.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <string_view>
#include <vector>

struct LongestCommonSubstringResult {
	int s_pos = 0, t_pos = 0, length = 0;
};

inline LongestCommonSubstringResult longest_common_substring(std::string_view s, std::string_view t) {
	[[maybe_unused]] constexpr std::size_t maximum = std::numeric_limits<int>::max() - 1;
	assert(s.size() <= maximum && t.size() <= maximum - s.size());
	if (s.empty() || t.empty()) return {};
	int n = int(s.size()), m = int(t.size()), bound = std::min(n, m);
	LongestCommonSubstringResult best{0, 0, sequence_compare_detail::prefix(s.data(), t.data(), bound)};
	if (best.length == bound) return best;
	if (auto match = substring_seed_detail::search(s, t, {best.s_pos, best.t_pos, best.length}))
		return {match->first, match->second, match->length};
	struct Joined {
		std::string_view s, t;
		int split;
		std::size_t size() const { return s.size() + t.size() + 1; }
		int operator[](int p) const {
			if (p < split) return static_cast<unsigned char>(s[p]) + 1;
			return p == split ? 0 : static_cast<unsigned char>(t[p - split - 1]) + 1;
		}
	};
	auto sa = suffix_array_detail::induced_sort(Joined{s, t, n}, 256);
	int size = int(sa.size());
	std::vector<int> rank(size);
	for (int i = 0; i < size; ++i) rank[sa[i]] = i;
	for (int p = 0, h = 0; p < size; ++p) {
		if (h) --h;
		if (!rank[p]) { h = 0; continue; }
		int q = sa[rank[p] - 1];
		if (q == n) { h = 0; continue; }
		bool first = p < n, other = q < n;
		int a = first ? p : p - n - 1, b = other ? q : q - n - 1;
		auto left = first ? s : t, right = other ? s : t;
		int limit = std::min(int(left.size()) - a, int(right.size()) - b);
		h += sequence_compare_detail::prefix(left.data() + a + h, right.data() + b + h, limit - h);
		if (first != other && h > best.length) {
			best = first ? LongestCommonSubstringResult{a, b, h} : LongestCommonSubstringResult{b, a, h};
			if (h == bound) return best;
		}
	}
	return best;
}

#endif

Back to top page