Go: package main

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

func max(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

/*********************************************************************
長さmの列X_(m)と長さnの列Y_(n)の最長共通部分列LCSは、
	(1)X[m] == Y[n]ならば、X_(m-1)とY_(n-1)のLCSにX[m]を繋げたもの
	(2)X[m] != Y[n]ならば、X_(m-1)とY_(n)のLCSもしくはX_(m)とY_(n-1)のLCS
	のいずれかのうち長い方

c[m+1][n+1]：c[i][j]にX_(i)とY_(j)のLCSの長さを格納する二次元配列
*********************************************************************/

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		scanner.Scan()
		s1 := scanner.Text()
		scanner.Scan()
		s2 := scanner.Text()
		s1, s2 = " " + s1 , " " + s2
		c := make([][]int, len(s1))
		for i := range c {
			c[i] = make([]int, len(s2))
		}

		LCS := 0

		for i := 1; i < len(s1); i++ {
			for j := 1; j < len(s2); j++ {
				if s1[i] == s2[j] {
					c[i][j] = c[i-1][j-1] + 1
				} else {
					c[i][j] = max(c[i-1][j], c[i][j-1])
				}
				LCS = max(LCS, c[i][j])
			}
		}
		fmt.Println(LCS)
	}
}

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: def ask(X,Y):

 a=len(X)
 b=len(Y)
 Z=[]
 c=0
 for n in range(a):
  z=0
  for i in range(n,a):
   for j in range(c,b):
    if(X[i]==Y[j]):
     z+=1
     c=j
     break
  Z.append(z)

 Z.sort();
 return Z[a-1]


q=int(input())
Z=[]
for p in range(q):
 x=input()
 X=list(x)
 y=input()
 Y=list(y)
 z=ask(X,Y)
 Z.append(z)

for p in range(q):
 print(Z[p])

Python: #!/usr/bin/env python3
import sys
sys.setrecursionlimit(15000)
n = int(sys.stdin.readline())

def lcs(X,Y):
  n_y = len(Y)
  n_x = len(X)
  #dp = [[0]*(n_x+1) for _ in range(n_y+1)]
  dp = [0]*(n_x+1)
  for i_y in range(n_y):
    ndp = dp.copy()
    for i_x in range(n_x):
      if X[i_x] == Y[i_y]:
        #dp[i_y+1][i_x+1] = dp[i_y][i_x] + 1
        ndp[i_x+1] = dp[i_x] + 1
      elif dp[i_x+1] < ndp[i_x]:
        #dp[i_y+1][i_x+1] = max(dp[i_y+1][i_x],dp[i_y][i_x+1])
        ndp[i_x+1] = ndp[i_x]
    dp = ndp
    #print(dp)
    #return(dp[-1][-1])
  return(dp[-1])

ret = []
inp = sys.stdin.readlines()
for i in range(n):
  X = inp[2*i].rstrip()#[:-1]#input()
  Y = inp[2*i+1].rstrip()#[:-1]#input()
  ret.append(lcs(X,Y))
  #print

print(*ret,sep="\n")

Python: n = int(input())

def lcs(x, y):
    xlen = len(x)
    ylen = len(y)
    if xlen == 0 or ylen == 0:
        return 0
    elif x[xlen-1] == y[ylen-1]:
        return lcs(x[:-1], y[:-1]) + 1
    else:
        return max(lcs(x, y[:-1]), lcs(x[:-1], y))

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

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

q=int(input())
A=[0 for i in range(q)]
for i in range(q):
    X=input()
    Y=input()
    A[i]=lcs(X,Y)

for i in range(q):
    print(A[i])

Python: """
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in xrange(len(s2) + 1)] for _ in xrange(2)]

	for i in xrange(1, len(s1) + 1):
		for j in xrange(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i & 1][j] = dp[1 - i & 1][j - 1] + 1
			else:
				dp[i & 1][j] = max(dp[1 - i & 1][j], dp[i & 1][j - 1])

	return dp[len(s1) & 1][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

Python: #JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            for x1 in range(Y[:y+1].count(X[x])):
                idx=now+Y[now:y+1].index(X[x])
                now=idx+1
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            now=0
            for y1 in range(X[:x+1].count(Y[y])):
                idx=now+X[now:x+1].index(Y[y])
                now=idx+1
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()