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: q = int(input())
alphabet =[chr(ord('a') + i) for i in range(26)]

for _ in range (q):
    S1 = list(input())
    S2 = list(input())
    S1.sort()
    S2.sort()
    count = 0
    for i in alphabet:
        temp = min(S1.count(i),S2.count(i))
        if temp !=0:
            count +=1
    print(count)

Python: #dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            else:
                row[j] = max(prerow[j],row[j-1])
    print(array[na][nb])

Python: n = int(input())
for i in range(n):
    a = input()
    b = input()
    L = [[0 for j  in range(len(a) + 1)] for k in range(len(b) + 1)]
    for  m in range(1, len(a) + 1):
        for n in range(1, len(b) + 1):
            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: 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])
                dp[J+1][i+1] = dp[j+1][i] if dp[j+1][i]>dp[j][i+1] else dp[j][i+1]
    print(dp[n][m])

Python: def longest_common(x, y):
  cost = [0]
  for c in y:
    for i in range(len(cost)-1, -1, -1):
      index = x.find(c, cost[i]) + 1
      if index:
        if i + 1 < len(cost):
          cost[i + 1] = min(cost[i+1], index)
        else:
          cost.append(index)
  return len(cost) -1

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

Python:  
def lcs(X, Y):
    dp = [0]*(len(Y)+1)
     
    for x in X:
        tmp = dp[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                                
    return dp[-1]
 
n = int(input()) 

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

Python: def solve():
  X,Y=input(),input()
  lx,ly=len(X),len(Y)
  dp=[0 for _ in range(ly+1)]
  
  for i in range(lx):
    tmp=dp+[]
    x=X[i]
    for j in range(ly):
      if x == Y[j]:
        dp[j+1]=tmp[j]+1
      elif dp[j] > dp[j+1]:
        dp[j+1]=dp[j]
  return dp[-1]

n=int(input())
for _ in range(n):
  print(solve())

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 main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence(X, Y))


if __name__ == '__main__':
    main()

Python: q = int(input())

l = []
x = ""
y = ""
"""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex == 0 and yIndex == 0:
        return 0
    elif xIndex == 0:
        return l[yIndex - 1][0]
    elif yIndex == 0:
        return l[0][xIndex - 1]
    elif x[xIndex] == y[yIndex]:
        return 1 + l[yIndex - 1][xIndex - 1]
    else:
        if l[yIndex][xIndex - 1] > l[yIndex - 1][xIndex]:
            return l[yIndex][xIndex - 1]
        else:
            return l[yIndex - 1][xIndex]
        #return max(l[yIndex][xIndex - 1], l[yIndex - 1][xIndex])
 """
for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * xLen for j in range(yLen)]

    for j in range(yLen):
        for k in range(xLen):
            if k == 0 and j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = 0
            elif k == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j - 1][k]
            elif j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j][k - 1]
            elif x[k] == y[j]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
            #l[j][k] = lcs(j, k)
 
    print(l[yLen- 1][xLen - 1])

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())

    r=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]

    for j in range(1,len(a)+1):
        for k in range(1,len(b)+1):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            if a[j-1]==b[k-1]:
                c=max(r[j-1][k-1]+1,r[j-1][k],r[j][k-1])
            
            r[j][k]=c
            print(r[j][k],end="")
        print(" ",end="\n")
    
    print(r[len(a)][len(b)])

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(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())
for k in range(q):
    x = input()
    y = input()
    print(Ics(x, y))

Python: q = int(input())

def lcs(X, Y):
    dp = [0]*(len(Y)+1)
    
    for x in X:
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                               
    return dp[-1]
    
for _ in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: def lcs_fast(x, y):
    len_x = len(x)
    len_y = len(y)

    c = [0] * (len_y + 1)
    for i in range(len_x):
        c_prev = c[:]
        for j in range(len_y):
            if x[i] == y[j]:
                c[j+1] = c_prev[j] + 1
            elif c[j+1] < c[j]:
                c[j+1] = c[j]
    return c[-1]


if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        x = input()
        y = input()
        # print(lcs(x, y))
        print(lcs_fast(x, y))

Python: 
def LCS(x, y):
    dp = {}
    for i in range(len(x)+1):
        dp[i] = {0: 0}
    for j in range(len(y)+1):
        dp[0][j] = 0
    
    for i in range(1, len(x)+1):
        for j in range(1, len(y)+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])
    
    return dp[len(x)][len(y)]

q = int(raw_input())
for i in range(q):
    X = raw_input()
    Y = raw_input()
    print(LCS(X, Y))