Реализации алгоритмов/Наибольшая общая подпоследовательность
Динамическое программирование
правитьПримеры реализации простого алгоритма динамического программирования со сложностью O(nm), где n, m — размеры строк.
string getLongestCommonSubsequence(const string& a, const string& b)
{
vector<vector<int> > max_len;
max_len.resize(a.size() + 1);
for(int i = 0; i <= static_cast<int>(a.size()); i++)
max_len[i].resize(b.size() + 1);
for(int i = static_cast<int>(a.size()) - 1; i >= 0; i--)
{
for(int j = static_cast<int>(b.size()) - 1; j >= 0; j--)
{
if(a[i] == b[j])
{
max_len[i][j] = 1 + max_len[i+1][j+1];
}
else
{
max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
}
}
}
string res;
for(int i = 0, j = 0; max_len[i][j] != 0 && i < static_cast<int>(a.size()) && j < static_cast<int>(b.size()); )
{
if(a[i] == b[j])
{
res.push_back(a[i]);
i++;
j++;
}
else
{
if(max_len[i][j] == max_len[i+1][j])
i++;
else
j++;
}
}
return res;
}
#>> a = "aaaaabbbb34354354345"
#>> b = "abbb34aaabbbb"
#>> longest_common_subsequence(a, b)
#=> "aaaabbbb"
def longest_common_subsequence(a, b)
max_len = Array.new(a.size + 1, 0)
max_len.map! {Array.new(b.size + 1, 0)}
(a.size - 1).downto(0) do |i|
(b.size - 1).downto(0) do |j|
if a[i] == b[j]
max_len[i][j] = 1 + max_len[i+1][j+1]
else
max_len[i][j] = [max_len[i+1][j], max_len[i][j+1]].max
end
end
end
res = ""
i = 0
j = 0
while max_len[i][j] != 0 && i < a.size && j < b.size
if a[i] == b[j]
res << a[i]
i += 1
j += 1
else
if max_len[i][j] == max_len[i+1][j]
i += 1
else
j += 1
end
end
end
res
end
require 'diff/lcs'
def lcs(x, y)
Diff::LCS.LCS(x, y).join
end
lcs(x = 'dggfgffegsss345265', y = 'vdfspkddssf4563')
#=> "dfsss456"
'''ещё один вариант:'''
def lcs(x, y)
dp = Array.new(x.length + 1){Array.new(y.length + 1){''}}
x.each_char.with_index do |c, i|
y.each_char.with_index do |d, j|
result = [dp[i][j], dp[i][j + 1], dp[i + 1][j]].max_by(&:length)
if c == d
result = dp[i][j] + c
end
dp[i + 1][j + 1] = result
end
end
dp[-1][-1]
end
lcs(x = 'dggfgffegsss345265', y = 'vdfspkddssf4563')
#=> "dfsss456"
import Data.Array
import Data.Function
import Data.List
yoba listY listX = reverse $ arr ! (lenY, lenX)
where lenY = length listY
lenX = length listX
arrY = listArray (1, lenY) listY
arrX = listArray (1, lenX) listX
arr = listArray ((0, 0), (lenY, lenX)) [value y x | y <- [0 .. lenY], x <- [0 .. lenX]]
value y x | y == 0 || x == 0 = []
| arrY ! y == arrX ! x = (arrY ! y :) $ arr ! (pred y, pred x)
| otherwise = maximumBy (compare `on` length) [arr ! (y, pred x), arr ! (pred y, x)]
main = print $ yoba "aaaaabbbb34354354345" "abbb34aaabbbb"
lcs([], _) ->
"";
lcs(_, []) ->
"";
lcs([X | T1], [X | T2]) ->
[X | lcs(T1, T2)];
lcs([X | T1] = L1, [Y | T2] = L2) when X =/= Y ->
longest(lcs(L1, T2), lcs(T1, L2)).
longest(T1, T2) when length(T1) >= length(T2) ->
T1;
longest(_, T2) ->
T2.