LCS(最長共通部分列) (dp/lcs.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

最長共通部分列(LCS)の長さを求める．

関数

• LCS(s1, s2)：文字列 s1 と s2 の最長共通部分列の長さを返す．
• LCS(v1, v2)：配列 v1 と v2 の最長共通部分列の長さを返す．

計算量

s1 の長さ（v1 の要素数）を $n$ ，s2 の長さ（v2 の要素数）を $m$ とする．

• $O(nm)$

Verified with

• test/aoj_ALDS1_10_C.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

int LCS(const string &s1, const string &s2) {
	vector<vector<int>> comlen(s1.length() + 1, vector<int>(s2.length() + 1, 0));

	for(int i = 1; i <= s1.length(); i++)
		for(int j = 1; j <= s2.length(); j++) {
			comlen[i][j] = max({comlen[i - 1][j], comlen[i][j - 1],
								comlen[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 1 : 0)});
		}

	return comlen[s1.length()][s2.length()];
}

template<typename T> int LCS(const vector<T> &v1, const vector<T> &v2) {
	vector<vector<int>> comlen(v1.length() + 1, vector<int>(v2.length() + 1, 0));

	for(int i = 1; i <= v1.length(); i++)
		for(int j = 1; j <= v2.length(); j++) {
			comlen[i][j] = max({comlen[i - 1][j], comlen[i][j - 1],
								comlen[i - 1][j - 1] + (v1[i - 1] == v2[j - 1] ? 1 : 0)});
		}

	return comlen[v1.length()][v2.length()];
}

#line 2 "dp/lcs.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

int LCS(const string &s1, const string &s2) {
	vector<vector<int>> comlen(s1.length() + 1, vector<int>(s2.length() + 1, 0));

	for(int i = 1; i <= s1.length(); i++)
		for(int j = 1; j <= s2.length(); j++) {
			comlen[i][j] = max({comlen[i - 1][j], comlen[i][j - 1],
								comlen[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 1 : 0)});
		}

	return comlen[s1.length()][s2.length()];
}

template<typename T> int LCS(const vector<T> &v1, const vector<T> &v2) {
	vector<vector<int>> comlen(v1.length() + 1, vector<int>(v2.length() + 1, 0));

	for(int i = 1; i <= v1.length(); i++)
		for(int j = 1; j <= v2.length(); j++) {
			comlen[i][j] = max({comlen[i - 1][j], comlen[i][j - 1],
								comlen[i - 1][j - 1] + (v1[i - 1] == v2[j - 1] ? 1 : 0)});
		}

	return comlen[v1.length()][v2.length()];
}

Back to top page