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 collections import defaultdict


def longest_common_subsequence(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[-1][-1]


def longest_common_subsequence2(s, t):
    dp = [0] * (len(t) + 1)
    for i in range(len(s)):
        si = s[i]
        tmp = dp[:]
        for j in range(len(t)):
            if si == t[j]:
                dp[j + 1] = tmp[j] + 1
            else:
                dp[j + 1] = max(dp[j + 1], dp[j])
    return dp[-1]


def main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence2(X, Y))


if __name__ == '__main__':
    main()

Python: import sys
N = int(input())

for _ in range(N):
    x = sys.stdin.readline()
    y = sys.stdin.readline()
    m, n = len(x), len(y)
    dp = [[0 for i in range(n+1)] for j 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]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
                
    print(dp[m][n])

Python: def main():
    n = int(input())
    result = []
    for i in range(n):
        a = input()
        b = input()
        array = [[1 for i in range(len(a))] for j in range(len(b))]
        for i in range(1, len(a)):
            for j in range(1, len(b)):
                c = 0
                if a[j] == b[i]:
                    c = 1
                array[i][j] = max(
                                    array[i-1][j],
                                    array[i][j-1],
                                    array[i-1][j-1]+c)
        result.append(array[len(a)-1][len(b)-1])
    for i in result:
        print(i)
if __name__ == "__main__":
    main()

Python: # -*- coding:utf-8 -*-
import sys


def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * y_length for i in range(x_length)]
    for i in range(x_length):
        for j in range(y_length):
            if i == 0 or j == 0:
                if x[i] == y[j]:
                    memo[i][j] = 1
                else:
                    memo[i][j] = 0
            elif x[i] == y[j]:
                memo[i][j] = memo[i-1][j-1] + 1
            else:
                memo[i][j] = max(memo[i-1][j], memo[i][j-1])
    return memo[i][j]


if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    for i in range(n):
        print(search(strs[i*2], strs[i*2+1]))

Python: n = int(input())
for i in range(n):
    a = input()
    b = input()
    la = len(a) + 1
    lb = len(b) + 1
    L = [[0 for j  in range(la)] for k in range(lb)]
    for  m in range(1, la):
        for n in range(1, lb):
            if a[m-1] == b[n-1]:
                L[n][m] = L[n-1][m-1] + 1
            else:
                L[n][m] = max(L[n-1][m], L[n][m-1])
    print(L[-1][-1])

Python: def get_longest_count(X, Y):
  offsets = [0]
  for y in Y:
    tmp = offsets[:]
    for i, o in enumerate(offsets):
      j = X.find(y, o)
      if j < 0: break
      if i < len(offsets) - 1:
        tmp[i + 1] = min(offsets[i + 1], j + 1)
      else:
        tmp.append(j + 1)
    offsets = tmp
  return len(offsets) - 1

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(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+=[z]
print(*map(len,a),sep='\n')

Python: def Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(b):
            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())
r = []
for k in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    r.append(Ics(s1, s2))

print(*r, sep = "/n")

Python: def LCS(S, T):
    LS = len(S); LT = len(T)
    if LT > LS:
        S, T = T, S
        LS, LT = LT, LS
    dp = [0] * (LT + 1)
    for s in S:
        dp_pre=dp[:]
        for j, t in enumerate(T):
            if s == t:
                dp[j + 1] = dp_pre[j] + 1
            elif dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]
    return dp[-1]

for _ in range(int(input())):
    print(LCS(input(), input()))

Python: def L(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    return A[-1]


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    print(L(str1,str2))

Python: q=int(input())
for i in range(q):
    s1=input()
    s2=input()
    ls1=len(s1)
    ls2=len(s2)
    f=[[0 for k in range(ls2+1)] for j in range(ls1+1)]
    for j in range(1,ls1+1):
        for k in range(1,ls2+1):
            if s1[j-1]==s2[k-1]:
                f[j][k]=f[j-1][k-1]+1
            else:
                f[j][k]=max(f[j-1][k],f[j][k-1])
    print(f[j][k])

Python: num = int(input())
for i in range(num):
    X = " " + input()
    Y = " " + input()
    lx = len(X)
    ly = len(Y)
    T = [0] * ly
    for j in range(1,lx):
        C = T[:]
        for k in range(1,ly):
            k1 = k-1
            if X[j] == Y[k]:
                T[k] = C[k1] + 1
            elif C[k] > T[k1]:
                T[k] = C[k]
            else:
                T[k] = T[k1]
        print(T[k])

Python: def lcs(X,Y,p,q,Z):
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i]==Y[j]:
                Z[i+1][j+1]=Z[i][j]+1
            else:
                if Z[i][j+1]>Z[i+1][j]:
                    Z[i+1][j+1]=Z[i][j+1]
                else:
                    Z[i+1][j+1]=Z[i+1][j]
    print(Z[p][q])

n=int(input())
for i in range(n):
    X=input()
    Y=input()
    p=len(X)
    q=len(Y)
    Z=[[0 for i in range(q+1)]for j in range(p+1)]
    lcs(X,Y,p,q,Z)

Python: q = int(input())
t = []
for i in range(q):
    X = input()
    Y = input()
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        c2 = c1[:]
        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])
    print(Ics(s1, s2))