Longest common subsequence

from functools import lru_cache

def lcs(a, b):
    @lru_cache(maxsize=None)
    def L(i, j):                      # LCS of a[:i] and b[:j]
        if i == 0 or j == 0:
            return 0
        if a[i - 1] == b[j - 1]:
            return 1 + L(i - 1, j - 1)
        return max(L(i - 1, j), L(i, j - 1))
    return L(len(a), len(b))

int lcs(const std::string& a, const std::string& b) {
    std::vector<std::vector<int>> memo(a.size() + 1, std::vector<int>(b.size() + 1, -1));
    std::function<int(int, int)> L = [&](int i, int j) {    // LCS of a[:i] and b[:j]
        if (i == 0 || j == 0) return 0;
        int& m = memo[i][j];
        if (m != -1) return m;
        if (a[i - 1] == b[j - 1]) return m = 1 + L(i - 1, j - 1);
        return m = std::max(L(i - 1, j), L(i, j - 1));
    };
    return L(a.size(), b.size());
}

static int lcs(String a, String b) {
    int[][] memo = new int[a.length() + 1][b.length() + 1];
    for (int[] row : memo) Arrays.fill(row, -1);
    return L(a, b, a.length(), b.length(), memo);
}

static int L(String a, String b, int i, int j, int[][] memo) {   // LCS of a[:i] and b[:j]
    if (i == 0 || j == 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    if (a.charAt(i - 1) == b.charAt(j - 1)) return memo[i][j] = 1 + L(a, b, i - 1, j - 1, memo);
    return memo[i][j] = Math.max(L(a, b, i - 1, j, memo), L(a, b, i, j - 1, memo));
}

function lcs(a, b) {
    const memo = new Map();
    const L = (i, j) => {                                  // LCS of a[:i] and b[:j]
        if (i === 0 || j === 0) return 0;
        const key = i * (b.length + 1) + j;
        if (memo.has(key)) return memo.get(key);
        const v = a[i - 1] === b[j - 1] ? 1 + L(i - 1, j - 1) : Math.max(L(i - 1, j), L(i, j - 1));
        memo.set(key, v);
        return v;
    };
    return L(a.length, b.length);
}

fn lcs(a: &[u8], b: &[u8]) -> usize {
    // LCS of a[..i] and b[..j]
    fn l(i: usize, j: usize, a: &[u8], b: &[u8], memo: &mut Vec<Vec<Option<usize>>>) -> usize {
        if i == 0 || j == 0 { return 0; }
        if let Some(v) = memo[i][j] { return v; }
        let v = if a[i - 1] == b[j - 1] { 1 + l(i - 1, j - 1, a, b, memo) }
                else { l(i - 1, j, a, b, memo).max(l(i, j - 1, a, b, memo)) };
        memo[i][j] = Some(v);
        v
    }
    let mut memo = vec![vec![None; b.len() + 1]; a.len() + 1];
    l(a.len(), b.len(), a, b, &mut memo)
}

lcs :: String -> String -> Int
lcs a b = t ! (m, n)
  where
    m = length a
    n = length b
    aa = listArray (1, m) a
    bb = listArray (1, n) b
    -- t ! (i, j): LCS of the first i characters of a and the first j of b
    t = array ((0, 0), (m, n)) [((i, j), cell i j) | i <- [0 .. m], j <- [0 .. n]] :: Array (Int, Int) Int
    cell 0 _ = 0
    cell _ 0 = 0
    cell i j
      | aa ! i == bb ! j = 1 + t ! (i - 1, j - 1)
      | otherwise = max (t ! (i - 1, j)) (t ! (i, j - 1))

def lcs_length(text1, text2):
    m = len(text2)
    prev = [0] * (m + 1)                       # row i - 1 of the table
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1       # match: extend the diagonal
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

#include <algorithm>
#include <string>
#include <vector>

int solve(std::string text1, std::string text2) {
    const int m = text2.size();
    std::vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (char ch : text1) {
        for (int j = 1; j <= m; ++j)
            cur[j] = ch == text2[j - 1] ? prev[j - 1] + 1 : std::max(prev[j], cur[j - 1]);
        std::swap(prev, cur);
    }
    return prev[m];
}

class Solution {
    public int lcsLength(String text1, String text2) {
        int m = text2.length();
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (char ch : text1.toCharArray()) {
            for (int j = 1; j <= m; j++)
                cur[j] = ch == text2.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
            int[] t = prev; prev = cur; cur = t;
        }
        return prev[m];
    }
}

function lcsLength(text1, text2) {
  const m = text2.length;
  let prev = new Array(m + 1).fill(0);
  for (const ch of text1) {
    const cur = new Array(m + 1).fill(0);
    for (let j = 1; j <= m; j++) cur[j] = ch === text2[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
    prev = cur;
  }
  return prev[m];
}

fn solve(text1: &str, text2: &str) -> i64 {
    let b: Vec<char> = text2.chars().collect();
    let m = b.len();
    let mut prev = vec![0i64; m + 1];
    for ch in text1.chars() {
        let mut cur = vec![0i64; m + 1];
        for j in 1..=m {
            cur[j] = if ch == b[j - 1] { prev[j - 1] + 1 } else { prev[j].max(cur[j - 1]) };
        }
        prev = cur;
    }
    prev[m]
}

solve :: String -> String -> Int
solve a b = last (foldl row (replicate (length b + 1) 0) a)
  where
    -- one row of the table from the previous row, for the character ch of the first string
    row prev ch = scanl step 0 (zip3 b prev (tail prev))
      where step left (c, diag, up) = if c == ch then diag + 1 else max up left