Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var q int
var X, Y string

func lcs(X, Y string) int {
	lenX := len(X)
	lenY := len(Y)
	dp := make([][]int, lenX+1)
	for i := 0; i < lenX+1; i++ {
		dp[i] = make([]int, lenY+1)
	}

	res := 0
	for i := 1; i < lenX+1; i++ {
		for j := 1; j < lenY+1; j++ {
			if X[i-1] == Y[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
			//fmt.Println(dp)
			res = maxInt(res, dp[i][j])
		}

	}
	return res
}

func main() {
	sc.Split(bufio.ScanWords)
	q = nextInt()

	for i := 0; i < q; i++ {
		X = nextStr()
		Y = nextStr()

		fmt.Println(lcs(X, Y))
	}
}

Python: # -*- coding: utf-8 -*-
def lcs(x, y):
    dp = {(0, 0): 0}
    for i in range(1, len(x) + 1):
        dp[(i, 0)] = 0
    for j in range(1, len(y) + 1):
        dp[(0, j)] = 0
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[(i, j)] = dp[(i - 1, j - 1)] + 1
            else:
                dp[(i, j)] = max(dp[(i - 1, j)], dp[(i, j - 1)])

    return dp[(len(x), len(y))]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))

Python: def solver(str_1 ,str_2):
  dp = [[0] * (len(str_2) + 1) for i in range(len(str_1) + 1)]
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
  return dp[len(str_2)][len(str_1)]

n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    c2 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        for j in range(n):
            if (d == Y[j]):
                c1[j + 1] = c2[j] + 1
            elif (c1[j + 1] < c1[j]):
                c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
t = []
for i in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Python: def f(i,j):
    if i == 0 or j == 0:
        if s1[i] == s2[j]:
            x[i][j] = 1
        else:
            if i == 0:
                x[i][j] = x[i][j-1]
            else:
                x[i][j] = x[i-1][j]
    elif s1[i] == s2[j]:
        x[i][j] = max(x[i-1][j-1]+1,x[i][j-1],x[i-1][j])
    else:
        x[i][j] = max(x[i-1][j-1],x[i][j-1],x[i-1][j])

n = int(input())
for i in range(n):
    s1 = input()
    s2 = input()
    x = [[0 for j in range(len(s2))]for k in range(len(s1))]
    for j in range(len(s1)):
        for k in range(len(s2)):
            f(j,k)
            
    print(x[len(s1)-1][len(s2)-1])

Python: import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                if primary[j] > match:
                    secondary[j] = primary[j]
                else:
                    secondary[j] = match
            else:
                sc1, p1, p2 = secondary[j-1], primary[j-1] + match, primary[j]
                if sc1 > p1:
                    if p1 > p2:
                        secondary[j] = sc1
                    elif p2 > sc1:
                        secondary[j] = p2
                    else:
                        secondary[j] = sc1
                else:
                    if sc1 > p2:
                        secondary[j] = p1
                    elif p1 > p2:
                        secondary[j] = p1
                    else:
                        secondary[j] = p2
                # secondary[j] = max(secondary[j-1], primary[j],
                #                    primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    input()
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, len(s), 2):
        print(len_lcs(s[i], s[i+1]))


if __name__ == '__main__':
    run()

Python: def solve_L():
    X = input()
    Y = input()
   
    a = len(X)
    b = len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = X[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == Y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input())
ans = [[] for i in range(n)]
for i in range(n):
    ans[i] = solve_L()
for i in range(n):
  print(ans[i])

Python: def lcs(x, y):

    l1, l2 = len(x), len(y)

    dp = [0] * (l2+1)
    #dp = [[0]*(l2+1) for i in range(l1+1)]

    for i in range(l1):
        prev = dp[:]
        for j in range(l2):
            if x[i] == y[j]:
                dp[j+1] = prev[j] + 1
                #dp[i+1][j+1] = dp[i][j] + 1   
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
    
    return dp[l2]

N = int(input())
ans = []
for i in range(N):
    x = input()
    y = input()
    ans.append(lcs(x,y))
for i in range(N):
    print(ans[i])

Python: #!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    n = int(stdin.readline())

    for _ in range(n):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()

        m = len(x)
        n = len(y)

        c = [[0]*(n+1) for _ in range(m+1)]

        cim1 = c[0]
        for i, xi in enumerate(x, start=1):
            ci = c[i]
            for j, yj in enumerate(y, start=1):
                if xi == yj:
                    ci[j] = cim1[j-1] + 1
                elif cim1[j] >= ci[j-1]:
                    ci[j] = cim1[j]
                else:
                    ci[j] = ci[j-1]
            cim1 = ci

        print(c[-1][-1])


main()

Python: def lcs_hs(s1, s2):
    from bisect import bisect_left

    p = []
    append_p = p.append
    for i, c in enumerate(s1):
        j = s2.find(c)+1
        while j:
            append_p((i, -j))
            j = s2.find(c, j)+1

    lis, result = [], 0
    append_lis = lis.append
    for _, y in sorted(p):
        i = bisect_left(lis, -y)
        if i >= result:
            append_lis(-y)
            result += 1
        else:
            lis[i] = -y

    return result


print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")