LCS の長さを計算する
-
// 実装の便宜上、配列の第 1 格から列を格納する。
-
int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};
-
int s2[5+1] = {0, 3, 5, 3, 2, 8};
-
// DP の表
-
int array[7+1][5+1];
-
void LCS()
-
{
-
array [x][0] と array [0][x] を両方 0 に設定する；
-
for (int i = 1; i <= s1_length; i++)
-
for (int j = 1; j <= s2_length; j++) -
if (s1[i] == s2[j]) -
// ここに加えた 1 は e1 の長さが 1 であることを示す -
array[i][j] = array[i-1][j-1] + 1; -
else -
array[i][j] = max(array[i-1][j], array[i][j-1]); -
cout <<"LCS の長さは" << array [seq1_length][seq2_length];
-
}
LCS を見つける
-
// 実装の便宜上、配列の第 1 格から列を格納する。
-
int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};
-
int s2[5+1] = {0, 3, 5, 3, 2, 8};
-
// DP の表
-
int array[7+1][5+1];
-
// この格の最大値がどの格から得られたかを記録する
-
int prev[7+1][5+1];
-
void LCS()
-
{
-
array [x][0] と array [0][x] を両方 0 に設定する；
-
for (int i = 1; i <= s1_length; i++)
-
for (int j = 1; j <= s2_length; j++) -
if (s1[i] == s2[j]) -
{ -
// ここに加えた 1 は e1 の長さが 1 であることを示す -
array[i][j] = array[i-1][j-1] + 1; -
prev[i][j] = 左上方; -
} -
else -
{ -
if (array[i-1][j] < array[i][j-1]) -
{ -
array[i][j] = array[i][j-1]; -
prev[i][j] = 左方; -
} -
else -
{ -
array[i][j] = array[i-1][j]; -
prev[i][j] = 上方; -
} -
} -
cout <<"LCS の長さは" << array [s1_length][s2_length];
-
cout << "LCS は";
-
print_LCS(s1_length, s2_length);
-
}
-
void print_LCS(int i, int j)
-
{
-
// 最初のまたは二番目のシーケンスが空のときに停止する
-
if (i==0 || j==0) return;
-
if (prev [i][j] == 左上方)
-
{
-
print_LCS(i-1, j-1); -
cout << s1[i]; // LCSの要素を出力する -
}
-
else if (prev [i][j] == 上方)
-
print_LCS(i-1, j); -
else if (prev [i][j] == 左方)
-
print_LCS(i, j-1); -
}