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())

l = []
x = ""
y = ""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex < 0 or yIndex < 0:
        return 0
    elif l[yIndex][xIndex] != -1:
        return l[yIndex][xIndex]
    elif x[xIndex] == y[yIndex]:
        return 1 + lcs(yIndex - 1, xIndex - 1)
    else:
        return max(lcs(yIndex, xIndex - 1), lcs(yIndex - 1, xIndex))

for i in range(q):
    x = input()
    y = input()

    l = [[-1] * len(x) for j in range(len(y))]

    for j in range(len(y)):
        for k in range(len(x)):
            l[j][k] = lcs(j, k)

    print(l[len(y)- 1][len(x) - 1])

Python: q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    print(dp1[-1])

Python: def calc_lcs(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0]*1001 for i in range(1000+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i][j - 1], c[i - 1][j]) 
            max_lcs = max(max_lcs, c[i][j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    for _ in range(num):
        X = input()
        Y = input()
        # X = 'abcbdab'
        # Y = 'bdcaba'


        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)

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

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))

Python: def lcs(a_str, b_str):
    dp = [[0 for n in range(len(a))] for m in range(len(b_str))]
    for i in range(len(b_str)):
        for j in range(len(a_str)):
            if i == 0 or j == 0:
                dp[i][j] = int(a_str[j] == b_str[i])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + int(a_str[j] == b_str[i]), dp[i - 1][j], dp[i][j - 1])
    return dp[len(b_str) - 1][len(a_str) - 1]

trial = int(input())

for _ in range(trial):
    a = input()
    b = input()
    print(lcs(a, b))

Python: e=input
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]
 print(len(z))

Python: import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
# 4/5??§Time Limit Exceeded 5.94s ????????????5s??\???????????????????????????



def prep_array(X, Y):
    """ ??????0???2?¬???????????????¨??????????????????????????\????????????????????§??????????????????????¨?(1000+1) """
    c = [[0]*1001 for _ in range(1000+1)]
    return c


def check_max(array):
    """ 2?¬????????????????????????§??????????????? """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§  ?§?
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j in range(1, n):
            if XX == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs3(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§7.1?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        XX = X[i]
        for j in range(1, n+1):
            if XX == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs2(X, Y, c):
    """
    c[i][j]????????¢????????????????????????????????§?????????????????¨?????????????????°??????????????????????????£??????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§8.2?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        for j in range(1, n+1):
            if X[i] == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs(X, Y, c):
    """
    ??????????????¢?????´????????????????????????????£?????????????
    4/5 ?????????????????????????????¨????????????????????????????????°??§12.5?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    return check_max(c)


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

        # ???????????????
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # ???????????¨???
        print(result)