Go: package main

import "fmt"

func initialize_grid(width int,height int)[][]int{
	var grid [][]int
	for i:=0;i<height+1;i++{
		var grid_row  []int
		for j:=0;j<width+1;j++{
			grid_row = append(grid_row,0)
		}
		grid = append(grid,grid_row[:])
	}
	return grid
}

func ma(x int,y int)int{
	if x >= y{
		return x
	}else{
		return y
	}
}

func main()  {
	//Take input
	var num int
	var st1,st2 string
	var string_pairs [][]string
	fmt.Scan(&num)
	for i:=0;i<num;i++{
		var string_pair []string
		fmt.Scan(&st1)
		fmt.Scan(&st2)
		string_pair = append(string_pair,st1,st2)
		string_pairs = append(string_pairs,string_pair)
	}
	//DP
	//initialize grid
	for i:=0;i<num;i++{
		string_1 := string_pairs[i][0]
		string_2 := string_pairs[i][1]

		dp := initialize_grid(len(string_2),len(string_1))

		for j:=1;j<len(string_1)+1;j++{
			for k:=1;k<len(string_2)+1;k++{
				if string_1[j-1] == string_2[k-1]{
					dp[j][k] = dp[j-1][k-1] + 1
				}else{
					dp[j][k] = ma(dp[j-1][k],dp[j][k-1])
				}
			}
		}
		fmt.Println(dp[len(string_1)][len(string_2)])
	}
}

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 l in range(ls1+1):
        f[l][0]=0
    for l in range(ls2+1):
        f[0][l]=0
    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: import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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)

q = INT()

for _ in range(q):
	S = input()
	T = input()
	print(lcs(S, T))

Python: q = int(input())

for k in range(q):
    x = input()
    y = input()
    lcs = [0 for i in range(len(x)+1)] 
    for i in range(1,len(y) + 1):
        lcs_2 = [i for i in lcs]
        for j in range(1,len(x) + 1):
            if x[j-1] == y[i-1]:
                lcs[j] = lcs_2[j-1] + 1  
    print(lcs[len(x)])

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

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Python: def lcs_len(x, y):
    ly = len(y)
    tcsl = [0 for i in range(ly + 1)]
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    print(tcsl[j])


import sys

q = int(sys.stdin.readline())

for i in range(q):
    ax = sys.stdin.readline()[:-1]
    ay = sys.stdin.readline()[:-1]
    lcs_len(ax, ay)

Python: # novel様のコードを借りて提出のテストです。失礼します
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 lcs(X, Y):
    x = len(X) + 1
    y = len(Y) + 1
    c = [[None for y in range(y)] for x in range(x)]
    for i in range(x):
        c[i][0] = 0
    for j in range(y):
        c[0][j] = 0

    for i in range(1, x):
        for j in range(1, y):
            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 c[x - 1][y - 1]

n = int(input())

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

Python: n = int(input())
dataset = []
for i in range(n):
    tmp = []
    tmp.append(input())
    tmp.append(input())
    dataset.append(tmp)

for data in dataset:
    m = len(data[0])
    n = len(data[1])
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))

    for j in range(n):
        for i in range(m):
            if data[0][i] == data[1][j]:
                dp[j+1][i+1] = dp[j][i] + 1
            else:
                dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])

    print(dp[n][m])

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

import random
import sys
import os
import pprint


def LCS(s0, s1):
    # print(s0)
    # print(s1)
    m = len(s0)
    n = len(s1)

    # memo[i][j]
    memo = [[0] * n for i in range(m)]
    # pprint.pprint(memo)

    # fill at index 0
    for i in range(m):
        if s1[0] in s0[0:i+1]:
            memo[i][0] = 1
    for j in range(n):
        if s0[0] in s1[0:j+1]:
            memo[0][j] = 1

    # fill memo
    for i in range(1, m):
        for j in range(1, n):
            # same last
            if s0[i] == s1[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[m-1][n-1]

#fd = os.open('ALDS1_10_C.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

n = int(input())
for _ in range(n):
    s0 = input()
    s1 = input()
    l = LCS(s0, s1)
    print(l)

Python: q = int(input())


for __ in range (q):

    S1 = input()
    S2 = input()
    dp = [[0 for i in range(len(S2)+1+10)] for j in range(len(S1)+1+10)]


    for i in range (len(S1)):
        for j in range (len(S2)):
            if S1[i] == S2[j]:
                dp[i+1][j+1] = max(dp[i+1][j]+1,dp[i+1][j]+1)
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    print(dp[len(S1)][len(S2)])

Python: def lcs(l1,l2):
    dp=[[0 for x in range(len(l2)+1)] for y in range(len(l1)+1)]

    for i in range(1,len(l1)+1):
        for j in range(1,len(l2)+1):
            if l1[i-1]==l2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                
    return dp[len(l1)][len(l2)]


a=[]
n=int(input())
for i in range(n):
    l1=list(input())
    l2=list(input())
    a+=[lcs(l1,l2)]

for i in range(n):
    print(a[i])

Python: m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for j in range(len(str1)):
        A_copy = A[:]
        for k in range(len(str2)):
            if(str1[j]==str2[k]):
                A[k+1] = A_copy[k]+1
            else:
                if(A[k] > A[k+1]):
                    A[k+1] = A[k]
    print(A[-1])