Go: package main

import (
	"fmt"
	"os"
	"strconv"
	"bufio"
	"strings"
	"sort"
)

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func f() {
	var S, T string
	fmt.Scan(&S)
	fmt.Scan(&T)
	lenS, lenT := len(S), len(T)
	dp := make([][]int, lenS+1)
	for i:=0; i<lenS+1; i++ {
		dp[i] = make([]int, lenT+1)
	}
	for i:=1; i<lenS+1; i++ {
		for j:=1; j<lenT+1; j++ {
			if S[i-1] == T[j-1] {
				dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	fmt.Println(dp[lenS][lenT])
}

func main(){
	var n int 
	fmt.Scan(&n)
	for i:=0; i<n; i++ {
		f()
	}
}

C++: #include<iostream>
#include<string>
int main()
{
  int n;
  int an[1000];
  int l=0;
  std::cin>>n;
  std::string x;
  std::string y;
  int ans[1000][1000];
  int j,k;
  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<1000;j++){
      for(int k=0;k<1000;k++){
	ans[j][k]=0;
      }
    }
    for(int j=1;j<x.size();j++){
      for(int k=1;k<y.size();k++){
	if(x[j]==y[k]){
	  ans[j][k]=ans[j-1][k-1]+1;
	}else{
	  if(ans[j][k-1]>ans[j-1][k]){
	    ans[j][k]=ans[j][k-1];
	  }else{
	    ans[j][k]=ans[j-1][k];
	  }
	}
      }
    }
    std::cout<<ans[x.size()-1][y.size()-1]<<'\n';  
  }
  return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[1001][1001];
int q;

void solve(){
  char x[1001],y[1001];
  scanf("%s %s",x,y);
  int lx = strlen(x);
  int ly = strlen(y);
  for(int i=0;i<=lx;i++){
    for(int j=0;j<=ly;j++){
      if(i==0||j==0) dp[i][j] = 0;
      else 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]);
    }
  }
  printf("%d\n",dp[lx][ly]);
  return;
}


int main(){
  scanf("%d",&q);
  for(int i=0;i<q;i++) solve();
  return 0;
}

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

int dp[1001][1001];
string s, t;
int n, m, a;

int main(){
  cin >> a;
  for(int b = 0; b < a; b++){
    cin >> s >> t;
    for(int i = 0; i <= 1000; i++)
      for(int j = 0; j <= 1000; j++) dp[i][j] = 0;
    m = s.size();
    n = t.size();
    for(int i = 1; i <= m; i++){
      for(int j = 1; j <= n; j++){
        if(s[i - 1] == t[j - 1]){
          dp[i][j] = dp[i-1][j-1] + 1;
        }
      else{
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }  
    cout << dp[m][n] << endl;
  }
  return 0;
}

C++: #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
static const int n=1000;

int lcs(string x,string y){
  int c[n+1][n+1];
  int m=x.size();
  int n=y.size();
  int maxl=0;
  x=' '+x;
  y=' '+y;
  for(int i=1;i<=m;i++)c[i][0]=0;
  for(int i=1;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-1][j],c[i][j-1]);
      }
      maxl=max(maxl,c[i][j]);
    }
  }
  /*  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
      cout<<c[i][j]<<" ";
    }
    cout<<endl;
    }///////////*/
  return c[m][n];
}

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++: #define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T>
bool chmin(T &a, const T &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}


int lcs(string X, string Y){
    int m = X.length(), n = Y.length();
    vector<VI> dp(m+1, VI(n+1, 0));

    FORS(i, 1, m){
        FORS(j, 1, n){
            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 dp[m][n];
}

int main(){
    int q; cin >> q;
    REP(i, q){
        string X, Y;
        cin >> X >> Y;
        cout << lcs(X, Y) << "\n";
    }
    return 0;
}

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

#define REP(i, n) for(int i = 0; i < (n); i++)

string str1, str2;
int dp[1001][1001];
int k;

int solve(int i, int j)
{
  if(dp[i][j] > 0)
    return dp[i][j];
  if(i == str1.size() || j == str2.size()){
    if(i != str1.size()){
      return solve(i + 1, k);
    }else{
      return 1;
    }
  }
  if(str1[i] == str2[j]){
    k = j + 1;
    dp[i][j] = solve(i + 1, j + 1);
    return dp[i][j] + 1;
  }else{
    return solve(i, j + 1);
  }
}

int main()
{
  int q, n, ans = 0;
  cin >> q;
  cin.ignore();
  fill(&dp[0][0], &dp[1001][0], -1);
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    REP(i, str1.size()){
      n = solve(i, 0) - 1;
      ans = (n > ans) ? n : ans;
    }
    cout << ans << endl;
    ans = 0;
  }
}