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<bits/stdc++.h>
using namespace std;

#define STR_MAX 1000

int mat[STR_MAX+1][STR_MAX+1];

int common_subsequence(int len1, int len2, string str1, string str2){
  int i, j;

  for(i=1; i<=len1; i++){
    for(j=1; j<=len2; j++){
      if(str1[i-1] == str2[j-1]) mat[i][j]=mat[i-1][j-1]+1;
      else mat[i][j]=max(mat[i-1][j], mat[i][j-1]);
    }
  }

  return mat[len1][len2];
}

int main(void){
  int i, n;
  string str1, str2;

  scanf("%d", &n);
  for(i=0; i<n; i++){
    cin >> str1 >> str2;

    int len1=str1.size(), len2=str2.size();
    printf("%d\n", common_subsequence(len1, len2, str1, str2));
  }
  
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
  int q; cin >> q;
  vector<vector<string>> retsu(150, vector<string>(2));
  rep(i, q) {
    cin >> retsu[i][0] >> retsu[i][1];
//    cout << retsu[i][0] << retsu[i][1] << endl;
  }
  
  rep(i, q) {
    string a_1 = retsu[i][0], a_2 = retsu[i][1];
    int b_1 = (int)a_1.size(), b_2 = (int)a_2.size();
//    cout << b_1 << b_2 << endl;
    
    int dp[b_1 + 1][b_2 + 1];
    memset(dp, 0, sizeof(dp));
    rep(j, b_1) {
      rep(k, b_2) {
        if (a_1[j] == a_2[k]) {
          dp[j+1][k+1] = dp[j][k] + 1;
        }
        else {
          dp[j+1][k+1] = max(dp[j+1][k], dp[j][k+1]);
        }
      }
    }
    
    cout << dp[b_1][b_2] << endl;
    
  }

}

C++: #include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <time.h>

using namespace std;

void solve(){
	int n, m;
	time_t start, end;

	cin >> n;
	string A;
	/*for (int i = 0; i < n; i++)*/ cin >> A;
	cin >> m;
	string B;
	cin >> B;
	vector<vector<int>> DP(n + 1, vector<int>(m + 1, 0));
	start = clock();
	
	//for (int i = 0; i < n; i++) DP[i][0] = 0;
	//for (int j = 0; j < m; j++) DP[0][j] = 0;

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (A[i - 1] == B[j - 1]) DP[i][j] = DP[i - 1][j - 1] + 1;
			else DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
		}
	}

	end = clock();

	cout << DP[n][m] << endl;

}

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		solve();
	}
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int main(){
  int N,X,Y;
  char x[1024],y[1024];
  int dp[1024][1024];
  scanf("%d",&N);
  while(N--){
    scanf("%s%s", x, y);
    X = strlen(x); Y = strlen(y);
    memset(dp, 0, sizeof dp);
    for(int i=0;i<X;i++){
      for(int j=0;j<Y;j++){
    if(x[i]==y[j]) dp[i+1][j+1] = dp[i][j]+1;
    else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
      }
    }
    printf("%d\n", dp[X][Y]);
  }
  return 0;
}

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

const int IMINUS_JMINUS = 1, IMINUS = 2, JMINUS = 3;

struct state
{
    int length, from;
};

void lcs(string &s, string &t)
{
    state dp[s.length() + 1][t.length() + 1];
    memset(dp, 0, sizeof(dp));
    
    //cout << dp[0][0].length << endl;
    for (int i = 1; i < s.length() + 1; i++) {
        for (int j = 1; j < t.length() + 1; j++) {
            //if (i == 5 && j == 2) {
            //    cout << "" << endl;
            //}
            if (s[i - 1] == t[j - 1]){
                if (dp[i][j].length < dp[i - 1][j - 1].length + 1)
                {
                    dp[i][j].length = dp[i - 1][j - 1].length + 1;
                    dp[i][j].from = IMINUS_JMINUS;
                }
            } else {
                if (dp[i][j].length < dp[i - 1][j].length)
                    dp[i][j].length = dp[i - 1][j].length, dp[i][j].from = IMINUS;
                if (dp[i][j].length < dp[i][j - 1].length)
                    dp[i][j].length = dp[i][j - 1].length, dp[i][j].from = JMINUS;
            }
            //cout << "i,j" << i << ", " << j << ":" <<  dp[i][j].length << endl;
        }
    }
    cout << dp[s.length()][t.length()].length << endl;
}

int main(int argc, char *argv[])
{
    
 
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s, t;
    while (n--) {
        cin >> s >> t;
        lcs(s, t);
    }
    
    
    
    return 0;
}

C++: #include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int dp[1010][1010];

int main(void){
	int i,j,k;

	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int q;
	cin >> q;
	for(i=0;i<q;i++){
		string x,y;
		cin >> x >> y;
		int n=x.size(),m=y.size();

		for(j=0;j<=n;j++) for(k=0;k<=m;k++) dp[j][k]=0;

		for(j=1;j<=n;j++){
			for(k=1;k<=m;k++){
				if(x[j-1]==y[k-1]) dp[j][k]=dp[j-1][k-1]+1;
				else dp[j][k]=max(dp[j][k-1],dp[j-1][k]);
			}
		}

		cout << dp[n][m] << endl;

	}

	return 0;
}

C++: #include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int dp[1001][1001];
int main() {
	int q; scanf("%d", &q);
	rep(i, q) {
		string x, y; cin >> x >> y;
		rep(i, x.size())rep(j, y.size()) {
			if (x[i] == y[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]);
		}
		printf("%d\n", dp[x.size()][y.size()]);
	}
}

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

int lcs(string str1, string str2)
{
	int len[1001][1001] = { 0 };

	int len1 = str1.length();
	int len2 = str2.length();
	//str1 = ' ' + str1;
	//str2 = ' ' + str2;

	for (int i = 0; i <= len1; i++)
		for (int j = 0; j <= len2; j++) len[i][j] = 0;

	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			if (str1[i] == str2[j]) len[i][j] = len[i - 1][j - 1] + 1;
			else len[i][j] = max(len[i - 1][j], len[i][j - 1]);
		}
	}
	return len[len1][len2];
}

int main()
{
	int n;
	string str1, str2;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> str1 >> str2;
		cout << lcs(str1, str2) << endl;
	}

	return 0;
}