Go: package main

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

const max int = 1000 + 1
var A [][]int

func lcs(x, y string) int {
	x = " " + x
	y = " " + y
	for i:=0;i<len(x); i++ {
		for j:=0;j<len(y); j++ {
			A[i][j] = 0
		}
	}
	for i:=1; i<len(x); i++ {
		for j:=1; j<len(y); j++ {
			if x[i] == y[j] {
				A[i][j] = A[i-1][j-1] + 1
			} else if A[i-1][j] > A[i][j-1] {
				A[i][j] = A[i-1][j]
			} else {
				A[i][j] = A[i][j-1]
			}
		}
	}
	return A[len(x)-1][len(y)-1]
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num 
}

func nextStr(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}


func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	A = make([][]int, max)
	for i := range A {
		A[i] = make([]int, max)
	}
	n := nextInt(scanner)
	for i:=0; i<n; i++ {
		x := nextStr(scanner)
		y := nextStr(scanner)
		fmt.Printf("%d\n", lcs(x, y))
	}
}

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

int lcs(string X, string Y) {
  int dp[1000 + 1][1000 + 1];
  int max = 0;
  X = ' ' + X;
  Y = ' ' + Y;
  for (unsigned int i = 1; i <= X.size() - 1; i++)
    dp[i][0] = 0;

  for (unsigned int i = 1; i <= Y.size() - 1; i++)
    dp[0][i] = 0;
  for (unsigned int i = 1; i <= X.size() - 1; i++) {
    for (unsigned int j = 1; j <= Y.size() - 1; j++) {
      if (X[i] == Y[i])
	dp[i][j] = dp[i - 1][j - 1] + 1;
      else if (dp[i - 1][j] >= dp[i][j - 1])
	dp[i][j] = dp[i - 1][j];
      else
	dp[i][j] = dp[i][j - 1];

      max = (max < dp[i][j]) ? dp[i][j] : max;
    }
  }

  return max;
}

int main(int argc, char const *argv[]) {
  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    string X, Y;
    cin >> X >> Y;

    cout << lcs(X, Y) << endl;
  }

  return 0;
}

C++: #include <stdio.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include <cassert>
#include <climits>
#include <vector>
#include <memory>
using namespace std;

#define DEBUG (0)

#if DEBUG
#define DPRINTF(...) do { \
    printf("D(L%d) %s: ", __LINE__, __func__); \
    printf(__VA_ARGS__); \
  } while (false)
#else
#define DPRINTF(...)
#endif // DEBUG


class LongestCommonSubsequence {
public:
  LongestCommonSubsequence(string s0, string s1) :
    s0_(s0),
    s1_(s1)
    {
      size_ = s0_.length() * s1_.length();
      pLongest_ = new int [size_];
      for (int i = 0; i < size_; i++)
        pLongest_[i] = kInvalid;
    }

  ~LongestCommonSubsequence()
  {
    if (pLongest_)
      free(pLongest_);
  }

  int getLCSlen();
  void printLength();

  const int kInvalid = -1;

private:
  string s0_;
  string s1_;
  int *pLongest_;
  int size_;

  int getIndex(int x, int y);
  int getLCSlenOf(int n0, int n1);
};

/*********************************
Input:
  x[0], x[1], x[2], ..., x[n-1]
  y[0], y[1], y[2], ..., y[m-1]

Algorithm:
  if x[n-1] == y[m-1]
    LCS(n-1, m-1) = LCS(n-2,m-2) + 1

  if x[n-1] != y[m-1]
    LCS(n-1, m-1) = max(LCS(n-2, m-1), LCS(n-1, m-2))

  LCS(0, *) = LCS(*, 0) = 0;

  a b c b d a b
  b d c a b a
*********************************/

int LongestCommonSubsequence::getLCSlen()
{
  int n0 = s0_.length() - 1;
  int n1 = s1_.length() - 1;
  return getLCSlenOf(n0, n1);
}


int LongestCommonSubsequence::getLCSlenOf(int n0, int n1)
{
  DPRINTF("n0 %d  n1 %d\n", n0, n1);

  assert(-1 <= n0 && n0 < static_cast<int>(s0_.length()));
  assert(-1 <= n1 && n1 < static_cast<int>(s1_.length()));

  if (n0 < 0  || n1 < 0)
    return 0;

  const int idx = getIndex(n0, n1);

  if (pLongest_[idx] != kInvalid)
    return pLongest_[idx];

  if (s0_[n0] == s1_[n1])
    pLongest_[idx] = getLCSlenOf(n0 - 1, n1 - 1) + 1;
  else
    pLongest_[idx] = max(getLCSlenOf(n0 - 1, n1), getLCSlenOf(n0, n1 - 1));

  return pLongest_[idx];
}


int LongestCommonSubsequence::getIndex(int x, int y)
{
  return y * s0_.length() + x;
}


void LongestCommonSubsequence::printLength()
{
  for (int i = 0; i < s0_.length(); i++)
    for (int j = 0; j < s1_.length(); j++)
      DPRINTF("pLongest_[%d][%d] %d\n", i, j, pLongest_[getIndex(i, j)]);
}


int main()
{
  int numOfPair;
  cin >> numOfPair; cin.ignore();

  DPRINTF("num of pair %d\n", numOfPair);

  for (int i = 0; i < numOfPair; i++)
  {
    string str0, str1;
    cin >> str0 >> str1; cin.ignore();

    DPRINTF("str0 %s  str1 %s\n", str0.c_str(), str1.c_str());

    LongestCommonSubsequence lcs(str0, str1);
    cout << lcs.getLCSlen() << endl;

#if (1) && DEBUG
    lcs.printLength();
#endif
  }

  return 0;
}

C++: #include <iostream>
#include <cmath>
#include <vector>
#include <cstring>

constexpr int MAX = 1000;
char ls[MAX];
char rs[MAX];
int table[MAX + 1][MAX + 1];


void calc_lcs() {
    scanf("%s", ls);
    scanf("%s", rs);
    int l_len = int(std::strlen(ls));
    int r_len = int(std::strlen(rs));
    for (int i = 0; i < l_len; i++) {
        table[i][0] = 0;
    }
    for (int i = 0; i < r_len; i++) {
        table[0][i] = 0;
    }

    for (int l_i = 1; l_i < l_len + 1; l_i++) {
        for (int r_i = 1; r_i < r_len + 1; r_i++) {
            if (ls[l_i - 1] == rs[r_i - 1]) {
                table[l_i][r_i] = table[l_i - 1][r_i - 1] + 1;
            } else {
                table[l_i][r_i] = std::max(table[l_i][r_i - 1], table[l_i - 1][r_i]);
            }
        }
    }
    std::cout << table[l_len][r_len] << std::endl;
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        calc_lcs();
    }
}

C++: //include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define d(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


LL q,lenX,lenY,dp[1001][1001];
string X,Y;

int do_dp(){
    REP(i,lenX+1)dp[i][0]=0;
    REP(i,lenY+1)dp[0][i]=0;
    FOR(i,1,lenX+1)FOR(j,1,lenY+1){
        dp[i][j]=max(max(dp[i-1][j-1]+(X[i-1]==Y[j-1]?1:0),dp[i-1][j]),dp[i][j-1]);
    }
    return dp[lenX][lenY];
}

int main(void){
    cin>>q;
    REP(i,2*q){
        if(i%2==0){
            cin>>X;
        }
        else{
            cin>>Y;
        }
        lenX=X.size();
        lenY=Y.size();
        if(i%2==1){
            cout<<do_dp()<<endl;
        }
    }
    return 0;
}