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: import sys

def dp_init(m, n):
    ret = []
    for i in range(m):
        ret.append([None] * n)
    return ret

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(len(str_a), len(str_b), str_a, str_b, dp, 0)

def rec(i, j, str_a, str_b, dp, depth):
    if dp[i-1][j-1] is not None:
        #print(dp)
        #print(" "*depth + "(%d, %d) : %d - hit" % (i-1, j-1, dp[i-1][j-1]))
        return dp[i-1][j-1]
    if i-1 == 0 or j-1 == 0:
        dp[i-1][j-1] = 0
        #print(" "*depth + "(%d, %d) : %d - zero" % (i-1, j-1, dp[i-1][j-1]))
        return 0
    if str_a[i-1] == str_b[j-1]:
        dp[i-1][j-1] = rec(i-1, j-1, str_a, str_b, dp, depth+1) + 1
        #print(" "*depth + "(%d, %d) : %d" % (i-1, j-1, dp[i-1][j-1]))
        return dp[i-1][j-1]

    dp[i-1][j-1] = max(rec(i, j-1, str_a, str_b, dp, depth+1), rec(i-1, j, str_a, str_b, dp, depth+1))
    #print(" "*depth + "(%d, %d) : %d" % (i-1, j-1, dp[i-1][j-1]))
    return dp[i-1][j-1]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

Python: from sys import stdin
input = stdin.readline

q = int(stdin.readline())

def solve():
    xs = input()
    ys = input()
    len_x = len(xs)-1
    len_y = len(ys)-1
    # [i,j]までで一番長い数値とする
    dp = [0] * (len_x+1)
    memo = [0] * (len_x+1)

    for j in range(len_y):
        yj = ys[j]
        # 参照コピーにならない
        memo = dp[:]
        for i in range(len_x):
            if xs[i] == yj:
                dp[i+1] = memo[i] + 1
            elif dp[i+1] < dp[i]:
                dp[i+1] = dp[i]
    return dp[len_x]


ret = [ solve() for i in range(q)]
print(*ret, sep="\n")

Python: def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()

Python: def lcs(X, Y):
    m, n = len(X), len(Y)
    memo = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                memo[i][j] = memo[i - 1][j - 1] + 1
            else:
                memo[i][j] = max(memo[i][j - 1], memo[i - 1][j])
    return memo[m][n]

n = int(input())
for _ in range(n):
    X, Y = input(), input()
    print(lcs(X, Y))

Python: def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)


n = int(input())
for _ in range(n):
    x = input()
    y = input()
    print(lcs(x, y))

Python: 
def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[1]*nb]*na
        #array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = array[i-1][j-1]+c 
                    max(
                            array[i-1][j],
                            array[i][j-1],
                            array[i-1][j-1]+c)
        print(array[na-1][nb-1])
if __name__ == "__main__":
    main()

Python: q = int(input())

for _ in range(q):
    X, Y = input(), input()
    n_X, n_Y = len(X), len(Y)

    dp = [[0 for _ in range(n_Y + 1)] for _ in range(n_X + 1)]
    for i in range(n_X):
        X_i = X[i]
        dp_i = dp[i]
        dp_i1 = dp[i + 1]
        for j in range(n_Y):
            if X_i == Y[j]:
                x = 1
            else:
                x = 0
            dp_i1[j + 1] = max(dp_i[j] + x, dp_i1[j], dp_i[j + 1])
    print(dp[n_X][n_Y])

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

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline



def calc_lcs4(X, Y):
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    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

    print(max_lcs)


if __name__ == '__main__':
    num = int(input())

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

        result = calc_lcs4(X, Y)

Python: def solve(X, Y):
    dp = [[0] * (len(Y)+1)]
    for i in range(1,len(X)+1):
        dp.append([0])
        for j in range(1,len(Y)+1):
            if X[i-1] == Y[j-1]:
                dp[i].append(dp[i-1][j-1] + 1)
            else:
                dp[i].append(max(dp[i-1][j], dp[i][j-1]))
    return dp[len(X)][len(Y)]

num = int(input())
for i in range(num):
    X = input()
    Y = input()
    print(solve(X,Y))

Python: e=input
a=[]
for _ in[0]*int(e()):
 X,z=e(),[]
 for y in e():
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 a+=[len(z)]
print(*a,sep='\n')

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 -*-
"""
Created on Fri May  4 20:33:37 2018
ALDS1_10_C Using Numpy
@author: maezawa
"""

import numpy as np

def longest(x, y):
    m = len(x)
    n = len(y)
    maxl = 0
    c = np.zeros((m+1, n+1), dtype=int)
    for i in range(m):
        for j in range(n):
            #print(i,j)
            if x[i] == y[j]:
                c[i, j] = c[i-1, j-1] + 1
            else:
                c[i, j] = max(c[i-1, j], c[i, j-1])
            maxl = max(maxl, c[i, j])
    return maxl

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(longest(x, y))