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<algorithm>
#include<string>
#include<vector>
#include<iostream>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b)
{
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

ll lcm(ll a,ll b)
{
   return a/gcd(a,b)*b;
}

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}
//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}

const ll MAX = 1000000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin>>n;
    vector<ll> ans(n);
    rep(i,n){
        string x,y;
        cin>>x>>y;
    
        ll dp[1010][1010]={0};
        rep(i,y.size()) dp[0][i]=0;
        
        rep(i,x.size()){
            for(ll j=0;j<y.size();j++){
                if(x.at(i)==y.at(j)) dp[i+1][j+1]=max(dp[i+1][j+1],1+dp[i][j]);
                else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
        ans[i]=dp[x.size()][y.size()];
    }
    rep(i,n) cout<<ans[i]<<endl;
    return 0;
}

C++: #include <iostream>
#include <string>
#define int long long
//#define _DEBUG
using namespace std;
string sa, sb;
int T[1000][1000];
int solve(){
    int sal = sa.length(), sbl = sb.length();
    for(int a=0; a<=sal; a++){
        for(int b=0; b<=sbl; b++){
            if(a==0 || b==0){
                T[a][b] = 0;
            }else if(sa[a-1] == sb[b-1]){
                T[a][b] = 1 + T[a-1][b-1];
            }else{
                T[a][b] = max(T[a][b-1], T[a-1][b]);
            }
        }
    }
    return T[sal][sbl];
}
signed main(){
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> sa >> sb;
        cout << solve() << endl;
    }
}

C++: #include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct LongestCommonSubstring{
  struct node{
    int value;
    node *next;
    node(int value,node *next):value(value),next(next){}
  };
  const int INF=1<<28;
  string x,y;
  LongestCommonSubstring(){}
  LongestCommonSubstring(string x,string y):x(x),y(y){}
  string lcs(){
    int n=x.size(),m=y.size();
    map<char,vector<int> > M;
    for(int j=m-1;j>=0;j--) M[y[j]].push_back(j);
    vector<int> xs(n+1,INF);
    xs[0]=-INF;
    vector<node* > link(n+1);
    for(int i=0;i<n;i++){
      if(M.count(x[i])){
	vector<int> ys=M[x[i]];
	for(int j=0;j<(int)ys.size();j++){
	  int k=distance(xs.begin(),lower_bound(xs.begin(),xs.end(),ys[j]));
	  xs[k]=ys[j];
	  link[k]=new node(y[ys[j]],link[k-1]);
	}
      }
    }
    string res;
    int l=distance(xs.begin(),lower_bound(xs.begin(),xs.end(),INF-1))-1;
    for(node *p=link[l];p!=NULL;p=p->next)
      res.push_back(p->value);
    return res;
  }
};
//END CUT HERE
signed main(){
  int q;
  cin>>q;
  while(q--){
    string x,y;
    cin>>x>>y;
    LongestCommonSubstring lcs(x,y);
    cout<<lcs.lcs().size()<<endl;
  }
  return 0;
}
/*
verified on 2017/06/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp
*/

C++: #if 0

#endif

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int Q;
int L[1000+10][1000+10];

int main() {
  cin >> Q;
  string X, Y;
  for (int i = 0; i < Q; i++) {
    for (int j = 0; j < 1000+10; j++) {
      L[0][j] = 0; L[j][0] = 0;
    }
    cin >> X >> Y;
    for (int x = 1; x <= X.length(); x++) {
      for (int y = 1; y <= Y.length(); y++) {
        if (X[x-1] == Y[y-1])
          L[x][y] = L[x-1][y-1] + 1;
        else
          L[x][y] = max(L[x-1][y], L[x][y-1]);
      }
    }
    cout << L[X.length()][Y.length()] << endl;
  }
}

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

int main(){
  int n;
  char x[1001],y[1001];
  int dp[1002][1002];
  


  //load n;
  cin >>n;
  for(int i=0;i<n;i++){
    //initialize
    for(int i=0;i<1002;i++){
      for(int j=0;j<1002;j++){
	dp[i][j]=0; 
      }
    }
    //load string
    scanf("%s",x);
    scanf("%s",y);
    //dp
    for(int j=0;j<strlen(x);j++){
      for(int k=0;k<strlen(y);k++){
	if(x[j]==y[k]){
	  dp[j+1][k+1]=dp[j][k]+1;
	}

	else{
 
	  if(dp[j][k+1]>dp[j+1][k]){
	    dp[j+1][k+1]=dp[j][k+1];
	  }

	  else{
	    dp[j+1][k+1]=dp[j+1][k];
	  }
	}
      }
    }

    //print
    cout <<dp[strlen(x)][strlen(y)]<<endl;
  }



  return 0;
}