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

C++: #include <iostream>
#include <algorithm>
#define MAX_N 1001
using namespace std;
//lcs
int n,m;
string s,t;
int dp[MAX_N+1][MAX_N+1];
void solve(){
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
      if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;
      else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
    }
  cout<<dp[n][m]<<endl;
}


int main(){
  int N;
  cin>>N;
  while(N--){
    cin>>s>>t;
    n=s.size();
    m=t.size();
    solve();
  }
  return 0;
}
//greatest common divisor
/*int main() {
  int a,b;
  cin >> a >>b;
  cout << __gcd(a,b)<<endl;
  return 0;
  }*/
//lcm
//__builtin_popcount()

//flymake
/*(require 'flymake)
 
(defun flymake-cc-init ()
(let* ((temp-file (flymake-init-create-temp-buffer-copy
'flymake-create-temp-inplace))
(local-file (file-relative-name
temp-file
(file-name-directory buffer-file-name))))
(list "g++" (list "-Wall" "-Wextra" "-fsyntax-only" local-file))))
 
(push '("\\.cpp$" flymake-cc-init) flymake-allowed-file-name-masks)
 
(add-hook 'c++-mode-hook
'(lambda ()
(flymake-mode t)))
(custom-set-variables
 '(ansi-color-names-vector ["#2d3743" "#ff4242" "#74af68" "#dbdb95" "#34cae2" "#008b8b" "#00ede1" "#e1e1e0"])
 '(custom-enabled-themes (quote (tsdh-light))))

*/

C++: #include <iostream>
#include <string>
#include <algorithm>

using namespace std;


static const int int N = 1000;


int lcs(string x, string y) {
    int c[N + 1][N + 1];
    int m = x.size();
    int n = y.size();
    int res = 0;

    x = ' ' + x;
    y = ' ' + y;

    for (int i = 0; i <= m; i++) c[i][0] = 0;
    for (int i = 0; i <= n; i++) c[0][i] = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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]);
            }
            res = max(res, c[i][j]);
        }
    }

    return 0;
}

int main() {
    string s1, s2;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl;
    }
    return 0;
}

C++: #include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main(void){
  string st1, st2;
  int q, val[151][151];

  cin >> q;

  for(int i=0; i<q; i++){
    cin>>st1;
    cin>>st2;

    for(int j=0; j<=st1.length(); j++){
      for(int k=0; k<=st2.length(); k++){

	if(j==0 || k==0) val[j][k] = 0;
	else{
	  if(val[j-1][k] == min(st1.length(), st2.length())){
	    val[j][k] = st1.length();
	  }else{

	    if(st1[j-1] == st2[k-1]){
	      val[j][k] = val[j-1][k-1]+1;
	    }else{
	      val[j][k] = max(val[j-1][k], val[j][k-1]);
	    }
	  }
	}
      }
    }

    for(int j=0; j<=st1.length(); j++){
      for(int k=0; k<=st2.length(); k++){
	cout << val[j][k] << " ";
      }
      cout << "\n";
    }
    

    cout << val[st1.length()][st2.length()] << "\n";
  }

  return 0;
}

C++: #include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
//#include<utility>
//#include<initializer_list>
//#include<tuple>
//#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
bool isSubstring(string substr, string t) {
	int n = substr.length();
	int seek = 0;
	rep(i, n) {
		bool ex = 0;
		for (int j = seek; j < t.length(); j++) {
			if (substr[i] == t[j]) {
				ex = 1;
				seek = j + 1;
				break;
			}
		}
		if (ex) {
			continue;
		}
		else {
			return false;
		}
	}
	return true;

}

int LongestCommonSubstring(string s, string t) {
	// Wrong plan
	vector<int>dp(s.length(), 0);
	int n = s.length();
	string lcs = "";
	if (isSubstring(s.substr(n - 1, n), t)) {

		dp[n - 1] = 1;
		lcs = s[n - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		//string substr = s.substr(i, n);
		string substr = s[i] + lcs;
		int issubst = isSubstring(substr, t);
		if (issubst) lcs = substr;
		dp[i] = dp[i + 1] + issubst;
	}
	return dp[0];
}
int LongestCommonSubstring2(string s, string t) {
	vector<vector<int>> dp(s.length() + 1, vector<int>(t.length() + 1, 0));
	int n = s.length() + 1;
	int m = t.length() + 1;
	rep(i, n - 1) {
		rep(j, m - 1) {
			dp[i + 1][j + 1] = s[i] == t[j] ? dp[i][j] + 1 : max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	return dp[n - 1][m - 1];
}
int main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring2("bacd", "becd") << endl;
	//cout << LongestCommonSubstring2("abcd", "becd") << endl;
	//cout << endl;
	cout << LongestCommonSubstring2("a", "a") << endl;
	cout << LongestCommonSubstring2("bbb", "bbb") << endl;
	cout << LongestCommonSubstring2("aba", "bbaba") << endl;
	cout << LongestCommonSubstring2("abababbbaa", "bbabaabba") << endl;
	cout << LongestCommonSubstring2("a", "aaaaa") << endl;
	cout << LongestCommonSubstring2("aizojfeiz", "aaaizojifeizz") << endl;
	cout << LongestCommonSubstring2("zzyiioxizu", "zzsyoizuo") << endl;
	cout << LongestCommonSubstring2("iooooioiooiio", "ooiiioioiooooiioio") << endl;
	cout << LongestCommonSubstring2("ajfoaooieellzljieoaelj", "ajoiiffoaolliseellzljieoaelj") << endl;
	cout << LongestCommonSubstring2("zzzzzyyzyy", "zzyyyyz") << endl;
	cout << LongestCommonSubstring2("abcdef", "fedcba") << endl;
	cout << LongestCommonSubstring2("abc", "xyz") << endl;
	int q;
	cin >> q;
	vector<string> s(q);
	vector<string> t(q);
	rep(i, q) {
		cin >> s[i] >> t[i];
	}
	rep(i, q) {
		cout << LongestCommonSubstring2(s[i], t[i]) << endl;
	}

	return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
  int n;
  cin >> n;
  for (int k=0;k<n;k++){
    string x,y;
    cin >> x >> y;
    int p=x.size();
    int q =y.size();
    int l[1001][1001] = {};
    for(int i=1;i<p+1;i++){
      for(int j=1;j<q+1;j++){
	if(x[i-1] == y[j-1] ){
	  l[i][j] = 1+l[i-1][j-1];
	}else{
	  l[i][j]= max(l[i-1][j],l[i][j-1]);
	}
      }
    }
    cout << l[p][q] << endl;
  }
}