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 REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int q; cin >> q;
  vector<string> X(q), Y(q); REP(i, q) cin >> X[i] >> Y[i];
  vector<vector<int>> dp(1010, vector<int>(1010));
  for(int i = 0; i < q; ++i) {
    REP(a, 1010) {
      REP(b, 1010) {
        dp[a][b] = 0;
      }
    }
    for(int k = 0; k < X[i].size(); ++k) {
      for(int m = 0; m < Y[i].size(); ++m) {
        if(X[i][k] == Y[i][m]) dp[k + 1][m + 1] = max(dp[k + 1][m + 1], dp[k][m] + 1);
        dp[k + 1][m + 1] = max(dp[k + 1][m + 1], dp[k + 1][m]);
        dp[k + 1][m + 1] = max(dp[k + 1][m + 1], dp[k][m + 1]);
      }
    }
    cout << dp[X[i].size()][Y[i].size()] << endl;
  }
}

C++: #include <iostream>
using namespace std;
static const int INFTY=(1<<21);

int main() {
  std::ios::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  int n;
  cin>>n;
  int p[n+1];
  for (int i=1; i<=n; i++) {
    cin>>p[i-1]>>p[i];
  }
  int m[n+1][n+1];
  for (int i=1; i<=n; i++) {
    m[i][i]=0;
  }
  for (int l=2; l<=n; l++) {
    for (int i=1; i<=n-l+1; i++) {
      int j=i+l-1;
      m[i][j]=INFTY;
      for (int k=i; k<=j-1; k++) {
        m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
      }
    }
  }
  cout<<m[1][n]<<endl;
  return 0;
}

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

static const int N = 1000;

int longestCommonSubsequence(string X, string Y)  {
  int c[N + 1][N + 1];
  int m = X.size();
  int n = Y.size();
  int max1 = 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]);
      }
      max1 = max(max1, c[i][j]);
    }
  }
  return max1;
}
 
int main()  {
  string s1, s2;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)  {
    cin >> s1 >> s2;
  cout << longestCommonSubsequence(s1, s2) << endl;
  }
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int q;
    cin >> q;
    for(int loop = 0; loop < q; ++loop){
        string s, t;
        cin >> s >> t;
        int n1 = s.length(), n2 = t.length();
        vector<vector<int>> dp(n1 + 2, vector<int>(n2 + 2, 0));
        for(int i = 0; i <= n1; ++i){
            for(int j = 0; j <= n2; ++j){
                chmax(dp[i][j + 1], dp[i][j]);
                chmax(dp[i + 1][j], dp[i][j]);
                if(i < n1 && j < n2 && s[i] == t[j]){
                    chmax(dp[i + 1][j + 1], dp[i][j] + 1);
                }
            }
        }
        cout << dp[n1][n2] << '\n';
    }
}

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

using namespace std;

void lcs(string x,string y){
  int m=x.length();
  int n=y.length();
  int c[m+1][n+1];
  for(int i=1;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-1]==y[j-1])
        c[i][j]=c[i-1][j-1]+1;
      else
        c[i][j]=max(c[i-1][j],c[i][j-1]);
    }
  }
  cout << c[m][n] << endl;
}

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

C++: #include <iostream>
#include <string>
#include <algprithm>
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++ ) {
		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;
}