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<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=0;i<=m;i++)c[i][0]=0;
  for(int j=1;j<=n;j++)c[0][j]=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]);
    }
  }
return maxl;
}

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<bits/stdc++.h>
using namespace std;
int a[1003][1003];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string x,y;
        cin>>x>>y;
        int len1=x.size();
        int len2=y.size();

        memset(a,0,sizeof(a));
        for(int i=0; i<len1; i++)
        {
            for(int j=0; j<len2; j++)
            {
                if(x[i]==y[j])
                {
                    a[i+1][j+1]=a[i][j]+1;
                }
                else a[i+1][j+1]=max(a[i][j+1],a[i+1][j]);
            }
        }
        cout<<a[len1][len2]<<endl;
    }

}

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

using namespace std;

int LCSLength(string X, string Y){
    int m = X.size();
    int n = Y.size();
    int c[m+1][n+1];
    int maxLength = 0;
    for(int i = 1; i <= m; i++) c[i][0] = 0;
    for(int j = 0; j <= n; j++) c[0][j] = 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 if(c[i-1][j] >= c[i][j-1]) c[i][j] = c[i-1][j];
            else c[i][j] = c[i][j-1];
            maxLength = max(maxLength, c[i][j]);
        }
    }
    return maxLength;
}

int main(){
    int n;
    string X, Y;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> X >> Y;
        cout << LCSLength(X, Y) << endl;
    }
    return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int lcs(string x, string y) {
    int lx = x.size(), ly = y.size();
    vector<vector<int>> dp(lx+1, vector<int>(ly+1, 0));
    for (int i=1;i<=lx; i++){
        for (int j=1; j<=ly; j++){
            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[lx][ly];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int q;
    cin >> q;
    for (int i=0;i<q;i++) {
        string x, y;
        cin >> x >> y;
        cout << lcs(x, y) << endl;
    }

    return 0;
}

C++: #include<string>
int lcs(std::string s, std::string t) {
    const int M = s.size(), N = t.size();
    int dp[M+1][N+1] = {};
    for(int i=0; i<M; ++i)
        for(int j=0; j<N; ++j)
            if(s[i] == t[j]) dp[i+1][j+1] = dp[i][j] + 1;
            else dp[i+1][j+1] = std::max(dp[i+1][j], dp[i][j+1]);
    return dp[M][N];
}
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        string s,t;
        cin>>s>>t;
        cout<<lcs(s,t)<<endl;
    }
}

C++: #include <stdio.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
int dp[1001][1001] = {};

int getLCS(string X, string Y)
{
    for (int i = 1; i <= X.size(); i++)
    {
        for (int j = 1; j <= Y.size(); j++)
        {
            dp[i][j] = X[i - 1] == Y[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[X.size()][Y.size()];
}

int main()
{
    int q;
    string X, Y;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> X >> Y;
        cout << getLCS(X, Y) << "\n";
    }
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0, sizeof(a))

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

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

int main(void){
    int q; cin >> q;
    REP(i,q){
        string S,T; cin >> S >> T;
        int dp[S.size()+1][T.size()+1]; CLR(dp);
        REP(i,S.size())REP(j,T.size()){
            if(S[i] == T[j]) chmax(dp[i+1][j+1], dp[i][j]+1);
            chmax(dp[i+1][j+1], dp[i][j+1]);
            chmax(dp[i+1][j+1], dp[i+1][j]);
        }
        cout << dp[S.size()][T.size()] << en;
    }
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[2][1010];
int main(){
  int q;
  cin>>q;
  for(int cn=0;cn<q;cn++){
    string x,y;
    cin>>x>>y;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<x.size();i++){
      int nw=i%2;
      int nt=!nw;
      for(int k=0;k<1010;k++)dp[nt][k]=0;
      for(int j=0;j<y.size();j++){
	if(j)dp[nw][j]=max(dp[nw][j],dp[nw][j-1]);
	if(x[i]==y[j])dp[nt][j+1]=max(dp[nt][j+1],dp[nw][j]+1);
	dp[nt][j]=max(dp[nt][j],dp[nw][j]);
      }
    }
    int ans=0;
    for(int i=0;i<1010;i++)ans=max(ans,dp[x.size()%2][i]);
    cout<<ans<<endl;
  }
  return 0;
}