Go: package main

import "fmt"

func initialize_grid(width int,height int)[][]int{
	var grid [][]int
	for i:=0;i<height+1;i++{
		var grid_row  []int
		for j:=0;j<width+1;j++{
			grid_row = append(grid_row,0)
		}
		grid = append(grid,grid_row[:])
	}
	return grid
}

func ma(x int,y int)int{
	if x >= y{
		return x
	}else{
		return y
	}
}

func main()  {
	//Take input
	var num int
	var st1,st2 string
	var string_pairs [][]string
	fmt.Scan(&num)
	for i:=0;i<num;i++{
		var string_pair []string
		fmt.Scan(&st1)
		fmt.Scan(&st2)
		string_pair = append(string_pair,st1,st2)
		string_pairs = append(string_pairs,string_pair)
	}
	//DP
	//initialize grid
	for i:=0;i<num;i++{
		string_1 := string_pairs[i][0]
		string_2 := string_pairs[i][1]

		dp := initialize_grid(len(string_2),len(string_1))

		for j:=1;j<len(string_1)+1;j++{
			for k:=1;k<len(string_2)+1;k++{
				if string_1[j-1] == string_2[k-1]{
					dp[j][k] = dp[j-1][k-1] + 1
				}else{
					dp[j][k] = ma(dp[j-1][k],dp[j][k-1])
				}
			}
		}
		fmt.Println(dp[len(string_1)][len(string_2)])
	}
}

C++: #include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
//#include<utility>
//#include<initializer_list>
//#include<tuple>
//#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
bool isSubstring(string substr, string t) {
	int n = substr.length();
	int seek = 0;
	rep(i, n) {
		bool ex = 0;
		for (int j = seek; j < t.length(); j++) {
			if (substr[i] == t[j]) {
				ex = 1;
				seek = j + 1;
				break;
			}
		}
		if (ex) {
			continue;
		}
		else {
			return false;
		}
	}
	return true;

}

int LongestCommonSubstring(string s, string t) {
	// Wrong plan
	vector<int>dp(s.length(), 0);
	int n = s.length();
	string lcs = "";
	if (isSubstring(s.substr(n - 1, n), t)) {

		dp[n - 1] = 1;
		lcs = s[n - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		//string substr = s.substr(i, n);
		string substr = s[i] + lcs;
		int issubst = isSubstring(substr, t);
		if (issubst) lcs = substr;
		dp[i] = dp[i + 1] + issubst;
	}
	return dp[0];
}
int LongestCommonSubstring2(string s, string t) {
	vector<vector<int>> dp(s.length() + 1, vector<int>(t.length() + 1, 0));
	int n = s.length() + 1;
	int m = t.length() + 1;
	rep(i, n - 1) {
		rep(j, m - 1) {
			dp[i + 1][j + 1] = s[i] == t[j] ? dp[i][j] + 1 : max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	return dp[n - 1][m - 1];
}
int main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring2("bacd", "becd") << endl;
	//cout << LongestCommonSubstring2("abcd", "becd") << endl;
	//cout << endl;
	//cout << LongestCommonSubstring2("a", "a") << endl;
	//cout << LongestCommonSubstring2("bbb", "bbb") << endl;
	//cout << LongestCommonSubstring2("aba", "bbaba") << endl;
	//cout << LongestCommonSubstring2("abababbbaa", "bbabaabba") << endl;
	//cout << LongestCommonSubstring2("a", "aaaaa") << endl;
	//cout << LongestCommonSubstring2("aizojfeiz", "aaaizojifeizz") << endl;
	//cout << LongestCommonSubstring2("zzyiioxizu", "zzsyoizuo") << endl;
	//cout << LongestCommonSubstring2("iooooioiooiio", "ooiiioioiooooiioio") << endl;
	//cout << LongestCommonSubstring2("ajfoaooieellzljieoaelj", "ajoiiffoaolliseellzljieoaelj") << endl;
	//cout << LongestCommonSubstring2("zzzzzyyzyy", "zzyyyyz") << endl;
	//cout << LongestCommonSubstring2("abcdef", "fedcba") << endl;
	//cout << LongestCommonSubstring2("abc", "xyz") << endl;
	int q;
	cin >> q;
	vector<string> s(q);
	vector<string> t(q);
	rep(i, q) {
		cin >> s[i] >> t[i];
	}
	rep(i, q) {
		cout << LongestCommonSubstring2(s[i], t[i]) << endl;
	}

	return 0;
}

C++: #include <bits/stdc++.h>
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++) c[i][0] = 0;
  for (int i = 1; i <= n; i++) c[0][i] = 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<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int LCS(string p, string q) {
	vector<vector<int> > f(p.size()+1, vector<int>(q.size()+1,0));
	int t;
	for (int i = 1; i <= p.size(); i++) {
		for (int j = 1; j <= q.size(); j++) {
			if (p[i-1] == p[j-1])
				f[i][j] = f[i - 1][j - 1] + 1;
			else if (f[i][j - 1] > f[i - 1][j - 1])
				f[i][j] = f[i][j - 1];
			else
				f[i][j] = f[i - 1][j];
		}
	}
	return f[p.size()][q.size()];
}

int main() {
	int n;
	string p[150];
	cin >> n;
	for (int i = 0; i < n; i ++) {
		cin >> p[2*i] >> p[2*i + 1];
	}
	for (int i = 0; i < n; i++) {
		cout << LCS(p[2*i], p[2 * i + 1])<<endl;
	}
	return 0;
}

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 = 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
      {
        c[i][j] = max(c[i][j - 1], c[i - 1][j]);
      }
      maxl = max(maxl, c[i][j]);
    }
  }
  return maxl;
}

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

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

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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;
int c[1001][1001];

int main() {
	int n;
	cin >> n;
	for (size_t r = 0; r < n; r++)
	{
		string s, t;
		cin >> s >> t;
		int p = s.size();
		int q = t.size();
		for (size_t i = 1; i < p+1; i++)
		{
			for (size_t j = 1; j < q+1; j++)
			{
				if(s[i-1] == t[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[p][q] << endl;
	}
	
}