Go: // AOJ ALDS1_10_C: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

package main

import (
	"fmt"
)

func main() {
	var dataNum int
	var s1, s2 string

	fmt.Scanf("%d", &dataNum)

	for i := 0; i < dataNum; i++ {
		fmt.Scanf("%s", &s1)
		fmt.Scanf("%s", &s2)

		lcs := make([][]int, len(s1)+1)
		for j := 0; j < len(s1)+1; j++ {
			lcs[j] = make([]int, len(s2)+1)
		}

		for m, vs1 := range s1 {
			for n, vs2 := range s2 {
				if vs1 == vs2 {
					lcs[m+1][n+1] = lcs[m][n] + 1
				} else if lcs[m+1][n] > lcs[m][n+1] {
					lcs[m+1][n+1] = lcs[m+1][n]
				} else {
					lcs[m+1][n+1] = lcs[m][n+1]
				}
			}
		}

		// Answer
		fmt.Println(lcs[len(s1)][len(s2)])
	}
}

Python: from typing import List


def compute_lcs(x_str: str, y_str: str) -> int:
    if len(x_str) <= len(y_str):
        shorter_str, longer_str = x_str, y_str
    else:
        shorter_str, longer_str = y_str, x_str

    lcs_idx: List[int] = []
    for s_ch in shorter_str:
        l_bgn_idx = 0
        for i, l_cur_idx in enumerate(lcs_idx):
            l_idx = longer_str.find(s_ch, l_bgn_idx)
            if -1 == l_idx:
                break
            lcs_idx[i] = min(l_cur_idx, l_idx)
            l_bgn_idx = l_cur_idx + 1  # Move to the next ch.
        l_idx = longer_str.find(s_ch, l_bgn_idx)
        if -1 != l_idx:
            lcs_idx.append(l_idx)
    return len(lcs_idx)


if __name__ == "__main__":
    num_pairs = int(input())

    for _ in range(num_pairs):
        x_str = input()
        y_str = input()
        lcs = compute_lcs(x_str, y_str)
        print(f"{lcs}")

Python: 
n=int(input())
cnt=[]
for k in range(n):
    a=input()
    b=input()
    lc=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i]==b[j]:
                lc[i+1][j+1]=lc[i][j]+1
            else:
                if lc[i][j+1]>lc[i+1][j]:
                    lc[i+1][j+1]=lc[i][j+1]
                else:
                    lc[i+1][j+1]=lc[i+1][j]
    cnt.append(lc[-1][-1])
for i in range(len(cnt)):
    print(cnt[i])

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
# 4/5??§Time Limit Exceeded 5.94s ????????????5s??\???????????????????????????



def prep_array(X, Y):
    """ ??????0???2?¬???????????????¨??????????????????????????\????????????????????§??????????????????????¨?(1000+1) """
    c = [[0]*1001 for _ in range(1000+1)]
    return c


def check_max(array):
    """ 2?¬????????????????????????§??????????????? """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§6.5?§?
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                row[j] = pre_row[j - 1] + 1
                if row[j] > max_lcs:
                    max_lcs = row[j]
            elif pre_row[j] >= row[j - 1]:
                row[j]= pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return max_lcs



def calc_lcs3(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§7.1?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        XX = X[i]
        for j in range(1, n+1):
            if XX == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs2(X, Y, c):
    """
    c[i][j]????????¢????????????????????????????????§?????????????????¨?????????????????°??????????????????????????£??????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§8.2?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        for j in range(1, n+1):
            if X[i] == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs(X, Y, c):
    """
    ??????????????¢?????´????????????????????????????£?????????????
    4/5 ?????????????????????????????¨????????????????????????????????°??§12.5?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    return check_max(c)


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

        # ???????????????
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # ???????????¨???
        print(result)

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())

    r=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]

    for j in range(1,len(a)+1):
        for k in range(1,len(b)+1):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            if a[j-1]==b[k-1]:
                c=max(r[j-1][k-1]+1,r[j-1][k],r[j][k-1])
            
            r[j][k]=c
            print(r[j][k],end="")
        print(" ",end="\n")
    
    print(r[len(a)][len(b)])

Python: def calc_lcs2(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0]*(m+1) for i in range(n+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    for row in c:
        max_lcs = max(row)
    return max_lcs



if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

        # ???????????????
        result = calc_lcs2(X, Y)

        # ???????????¨???
        print(result)

Python: q = int(input())
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    print(c[-1])

Python: def lcs_rec(i, j):
    if i == 0 or j == 0:
        return 0

    if X[i - 1] == Y[j - 1]:
        return lcs_rec(i - 1, j - 1) + 1
    else:
        return max(lcs_rec(i - 1, j), lcs_rec(i, j - 1))

q = int(input())

for i in range(q):
    X = input()
    Y = input()

    ans = lcs_rec(len(X), len(Y))

    print(ans)