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: n=int(input())
al=[]
bl=[]
for i in range(n):
	al.append(list(input()))
	bl.append(list(input()))

for i in range(n):
	a=al.pop(0)
	b=bl.pop(0)
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	if a[0]==b[0]:
		dp[0][0]=1
	for i in range(1,len(a)):
		if a[i]==b[0]:
			dp[i][0]=1
		else:
			dp[i][0]=dp[i-1][0]
	for i in range(1,len(b)):
		if a[0]==b[i]:
			dp[0][i]=1
		else:
			dp[0][i]=dp[0][i-1]
	for i in range(1, len(a)):
		for j in range(1, len(b)):
			if a[i]==b[j]:
				dp[i][j]=dp[i-1][j-1]+1
			else:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])

	print(dp[len(a)-1][len(b)-1])

Python: q = int(input())


def lcs(X, Y):
    x_len = len(X)
    y_len = len(Y)
    dp = [[0 for _ in range(y_len+1)] for _ in range(x_len+1)]
    
    for i in range(1, x_len+1):
        for j in range(1, y_len+1):
            if X[i-1] == Y[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 max(max(dp))
    
for _ in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: def lcs(str1,str2):
    c=[[0 for _ in range(1010)] for _ in range(1010)]
    m=len(str1)
    n=len(str2)
    maxl=0
    str1=" "+str1
    str2=" "+str2

    i=1
    j=1
    while(i<=m):
        while(j<=n):
            if(str1[i]==str2[j]):
                c[i][j]=c[i-1][j-1]+1
              #  print(c[i][j])
            else:
                c[i][j]=max(c[i-1][j],c[i][j-1])
            maxl=max(maxl,c[i][j])
            j+=1
        i+=1
        j=0

    return maxl

def main():
    n=int(input())
    i=0
    while(i<n):
        str1=str(input())
        str2=str(input())
        print(int(lcs(str1,str2)))
        i+=1

main()

Python: def edit_distance(s, t):
 s = raw_input()
 t = raw_input()
 dp = {}
 for i in range(len(s) + 1):
  dp[i] = {0: i}
 for j in range(len(t) + 1):
  dp[0][j] = j
 for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
   if (s[i-1] == t[j-1]): 
    d = 0
   else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
 return dp[len(s)][len(t)]
n = input()

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  s=0
  for i,k in enumerate(z):
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))

Python: # dpテーブル生成
def gen_dp(row, col):
  print('row: {}'.format(row))
  print('col: {}'.format(col))
  print('----------')
  return [[0]*col for i in range(row)]
#dpテーブル表示
def show_dp(table):
  for line in range(len(table)):
    print(table[line])
  print('----------')

def solver(str_1 ,str_2):
  # テーブル生成
  dp = gen_dp(len(str_2) + 1, len(str_1) + 1)
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      print('[str_2]:{}, [str_1]:{}'.format(r + 1, c + 1))
      # 末尾の文字が一致していれば
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      # 末尾の文字が違えば
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
      show_dp(dp)
  return dp[len(str_2)][len(str_1)]

# 実行
n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: i=input
for _ in[0]*int(i()):
 X,z=i(),[]
 for y in i():
  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]
 print(len(z))

Python: def gen_dp(row, col):
  return [[0]*col for i in range(row)]

def solver(str_1 ,str_2):
  dp = gen_dp(len(str_2) + 1, len(str_1) + 1)
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
  return dp[len(str_2)][len(str_1)]

n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: q = int(input())
 
def lcss(x,y):
     
    lcs = [0]*(len(x)+1)
    for i in range(len(y)):
        w1 = y[i]
        lcs_2 = lcs[:]
        for j in range(len(x)):
            if x[j] == w1:
                lcs[j+1] = lcs_2[j] + 1  
            elif lcs[j+1] < lcs[j]:
                lcs[j+1] = lcs[j]
    return lcs[-1]
 
for i in range(q):
    x = input()
    y = input()
    print(lcss(x,y))

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: pcsl = [[0] * 1001] * 1001

def lcs(x, y):
    m = len(x)
    n = len(y)
    for i in range(m):
        for j in range(n):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            elif pcsl[i - 1][j] > pcsl[i][j - 1]:
                pcsl[i][j] = pcsl[i - 1][j]
            else:
                pcsl[i][j] = pcsl[i][j - 1]
    print(pcsl[i][j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs(ax, ay)

Python: def num_substr(s, t):
    dp = {}
    for i in range(len(s) + 1):
        dp[i] = {0: 0}
    for j in range(len(t) + 1):
        dp[0][j] = 0
    
    for i in range(1,len(s)+1):
        Flag=False
        for j in range(1,len(t)+1):
            d=1 if s[i-1] == t[j-1] and dp[i-1][j-1] == dp[i][j-1] else 0
            dp[i][j] = max(dp[i-1][j] ,
                           dp[i][j-1] +d)
    return dp[len(s)][len(t)]

n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Python: # Longest Common Subsequence problem: LCS
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_C

import sys
input = sys.stdin.readline
ascii_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'


def get_LCS(x: str, y: str):
    lx = len(x)
    ly = len(y)
    dp = [[0] * (lx + 1) for _ in range(ly + 1)]  # 1-indexed

    for i in range(1, lx + 1):
        for j in range(1, ly + 1):
            if x[i - 1] == y[j - 1]:
                dp[j][i] = dp[j - 1][i - 1] + 1
            else:
                dp[j][i] = max(dp[j][i - 1], dp[j - 1][i])

    return dp[-1][-1]


def llcs(x, y):
    """solution author: bs5lNkJ"""
    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


n = int(input())

for _ in range(n):
    X = input().strip()
    Y = input().strip()
    print(llcs(X, Y))

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  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]
 print(len(z))