Go: package main

import (
	. "fmt"
    "math"
)

// func init() { Println("----------------------------------------") }

func main() {
    const L_MAX = 1003

	var q int
	Scanf("%d", &q)
	X := make([]string, 0, 150)
	Y := make([]string, 0, 150)
	for i := 0; i < 2 * q; i++ {
	    var tmp string
	    Scanf("%s", &tmp)

	    if i % 2 == 0 {
	        X = append(X, tmp)
	    } else {
	        Y = append(Y, tmp)
	    }
	}

    for i := 0; i < q; i++ {
        dp := make([][]int, L_MAX)
        for k, _ := range dp {
            dp[k] = make([]int, L_MAX)
        }

        x, y := X[i], Y[i]

        // init
        isXFound := false
        for c := 0; c < len(x); c++ {
            if isXFound || y[0] == x[c] {
                dp[0][c] = 1
                isXFound = true
            }
        }
        isYFound := false
        for r := 0; r < len(y); r++ {
            if isYFound || x[0] == y[r] {
                dp[r][0] = 1
                isYFound = true
            }
        }

        for r := 1; r < len(y); r++ {
            for c := 1; c < len(x); c++ {
                // dp[r][c]
                if x[c] == y[r] {
                    dp[r][c] = int(math.Max(float64(dp[r - 1][c - 1] + 1), float64(dp[r][c])))
                }

                dp[r][c] = int(math.Max(float64(dp[r][c]), math.Max(float64(dp[r - 1][c]), float64(dp[r][c - 1]))))
            }
        }
        Println(dp[len(y) - 1][len(x) - 1])

        // LCSも求めておく
        // ans := ""
        // r, c := len(y) - 1, len(x) - 1
        // for r >= 0 && c >= 0 {
        //     if y[r] == x[c] {
        //         ans = string(x[c]) + ans
        //         r--
        //         c--
        //     } else {
        //         if dp[r - 1][c] > dp[r][c - 1] {
        //             r--
        //         } else {
        //             c--
        //         }
        //     }
        // }
        // Println(ans)
    }
}

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

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    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):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    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:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

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

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)

Python: N = int(input())

for _ in range(N):
    x = input()
    y = input()
    m, n = len(x), len(y)
    dp = [0] * (n+1)
    
    for xi in x:
        temp = dp[:]
        for j in range(n):
            if xi == y[j]:
                dp[j+1] = temp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                
    print(dp[-1])

Python: q = int(input())
ans = []
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans.append(dp1[-1])
print(*ans, sep="\n")

Python: from __future__ import print_function
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(n + 1) for a in range(m + 2)]
    for i in xrange(1, m + 1):
        for j in xrange(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))
 
n = int(raw_input().rstrip())
strs = stdin.readlines()
ret = []
for i in xrange(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Python: ascii_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

def llcs(x, y):
    pm = dict((zip(ascii_letters, [0] * 52)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
    
    ans = bin(V)[-len(x):].count('0')
    
    return ans

from sys import stdin

def solve():
    file_input = stdin
    q = int(file_input.readline())
    for i in range(q):
        s1 = file_input.readline().rstrip()
        s2 = file_input.readline().rstrip()
        print(llcs(s1, s2))

solve()

Python: import sys

input = sys.stdin.readline


def solve(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i, x in enumerate(X, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j, y in enumerate(Y, start=1):
            if x == y:
                dp_i[j] = dp_im[j - 1] + 1
            elif dp_im[j] > dp_i[j - 1]:
                dp_i[j] = dp_im[j]
            else:
                dp_i[j] = dp_i[j - 1]
    return dp[m][n]


def main():
    q = int(input())
    X = [None] * q
    Y = [None] * q
    for i in range(q):
        X[i] = input().rstrip()
        Y[i] = input().rstrip()

    ans = [solve(x, y) for x, y in zip(X, Y)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Python: def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (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().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Python: # -*- coding: utf-8 -*-
 
 
def main(x, y):
    answer = 0
    x_len = len(x) + 1
    y_len = len(y) + 1
    array = [[0] * y_len] * x_len
    # x[0] == y[0] ?????´??????????????????????????¨??????????????????
    x = ' ' + x
    y = ' ' + y
    for i in range(1, x_len):
        for j in range(1, y_len):
            if x[i] == y[j]:
                array[i][j] = array[i - 1][j - 1] + 1
            else:
                array[i][j] = max(array[i][j - 1], array[i - 1][j])
            answer = max(answer, array[i][j])
    return answer

if __name__ == '__main__': 
    n = int(input())
    for _ in range(n):
        x = input()
        y = input()
        print(main(x, y))

Python: for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0 for y in range(len(Y)+1)] for x in range(len(X)+1)]
    for x in range(len(X) + 1):
        for y in range(len(Y) + 1):
            if x == 0 or y == 0:
                dp[x][y] = 0
            elif X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            else:
                dp[x][y] = max(dp[x-1][y], dp[x][y-1])
    print(dp[-1][-1])