Реализации алгоритмов/Наибольшая общая подпоследовательность

Динамическое программирование

Примеры реализации простого алгоритма динамического программирования со сложностью O(nm), где n, m — размеры строк.

C++

    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;
    }

Ruby

#>> 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

Ruby

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"

Haskell

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"

Erlang

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.