Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

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

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	for i := 0; i < n; i++ {
		x := getNextString(scanner)
		y := getNextString(scanner)

		fmt.Fprintln(writer, lcs(x, y))
	}

	writer.Flush()
}

func lcs(x, y string) int {
	lx := len(x)
	ly := len(y)
	dp := make([][]int, lx+1)
	for i := 0; i <= lx; i++ {
		dp[i] = make([]int, ly+1)
	}
	for i := 0; i < lx; i++ {
		for ii := 0; ii < ly; ii++ {
			if x[i] == y[ii] {
				dp[i+1][ii+1] = dp[i][ii] + 1
				continue
			}
			dp[i+1][ii+1] = dp[i][ii+1]
			if dp[i+1][ii] > dp[i+1][ii+1] {
				dp[i+1][ii+1] = dp[i+1][ii]
			}
		}
	}
	return dp[lx][ly]
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map <char,vector<int>> alx,aly;//x,y
int memo[1010][1010];
string x,y,q;
int lcs(int xn,int yn){//yn文字目以降でX[xn]と同じやつを探す
    if(memo[xn][yn]!=-1)return memo[xn][yn];
    int ans=0;
	/*
    for(int i=xn; i<x.size();i++){
        for(int j=yn; j<y.size(); j++){
            if(alx[x[i]]==aly[y[j]]){
                ans=max(ans,lcs(i+1,j+1)+1);
            }
        }
    }
	*/
	for(int i=xn; i<x.size();i++){
        for(int j=0; j<aly[x[i]].size(); j++){
			if(aly[x[i]][j] < yn) continue;
			ans=max(ans,lcs(i+1,aly[x[i]][j]+1)+1);
		}
    }
    return memo[xn][yn]=ans;
}
 
 
int main(){
    int q;
    cin >> q;
    for(int ds=0; ds<q; ds++){
 
        cin >> x >> y;
        for(int i=0; i<=x.size(); i++){
            for(int j=0; j<=y.size(); j++){
				memo[i][j]=-1;
			}
        }

		for(int i=0; i<x.size(); i++) alx[x[i]].push_back(i);
		for(int i=0; i<y.size(); i++) aly[y[i]].push_back(i);
		

        //memset(memo, -1, sizeof(memo));
         
        cout << lcs(0,0) << endl;
 
    }
    return 0;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)

string str1, str2;
int dp[1001][1001];

void solve()
{
  REP(i, str1.size())
    if(str1[i] == str2[str2.size() - 1])
      dp[i][str2.size() - 1] = 1;
    else
      dp[i][str2.size() - 1] = 0;
  for(int i = str2.size() - 2; i >= 0; i--)
    if(str1[str1.size() - 1] == str2[i])
      dp[str1.size() - 1][i] = 1;
    else
      dp[str1.size() - 1][i] = dp[str1.size() - 1][i + 1];
  for(int i = str1.size() - 2; i >= 0; i--){
    for(int j = str2.size() - 2; j >= 0; j--){
      if(str1[i] == str2[j])
	dp[i][j] = dp[i + 1][j + 1] + 1;
      else
	dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }
}
  
int main()
{
  int q;
  cin >> q;
  cin.ignore();
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    fill(&dp[0][0], &dp[1001][0], -1);
    solve();
    cout << dp[0][0] << endl;
  }
}

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

#define MAX_N 1000
#define MAX_M 1000

void solve();

string s, t;
int dp[MAX_N + 1][MAX_M + 1];

void solve(){
	for(int i = 0; i < s.length(); i++){
		for(int j = 0; j < t.length(); j++){
			if(s[i] == t[j]){
				dp[i + 1][j + 1];
					dp[i + 1][j + 1] = dp[i][j] + 1;
				} else {
					dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][j]);
				}
			}
		}
		cout << dp[s.length()][t.length()] << endl;
}

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> s >> t;
		solve();
	}
	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 = 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] == 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 q;
  cin >> q;

  for ( int i = 0; i < q; i++ ) {
    cin >> s1 >> s2;
    cout << lcs(s1, s2) << endl;
  }

  return 0;
}

C++: #include<iostream>
#include<string>
#include<string.h>

using namespace std;

int lcs(char x[],char y[]);

int main(){
	char x[1000],y[1000];
	int n,*memo; cin>>n;
	memo = new int[n];
	for(int i=0;i<n;i++){
		cin>>x>>y;
		memo[i] = lcs(x,y);
	}
	for(int i=0;i<n;i++)
		cout<<memo[i]<<endl;

	delete [] memo;
}

int lcs(char x[],char y[]){
	int m = strlen(x), n = strlen(y);
	int **c,a;
	c = new int*[m+1]; for(int i=0;i<=m;i++) c[i] = new int[n+1];
	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-1]==y[j-1]){
				c[i][j] = c[i-1][j-1]+1;
				if(i==m&&j==n){
					a = c[i][j];
					//cout<<c[i][j]<<endl;
				}
			}else{
				if(c[i-1][j]>=c[i][j-1]){
					c[i][j] = c[i-1][j];
					if(i==m&&j==n){
						a = c[i][j];
						//cout<<c[i][j]<<endl;
					}
				}else{
					c[i][j] = c[i][j-1];
					if(i==m&&j==n){
						a = c[i][j];
						//cout<<c[i][j]<<endl;
					}
				}
			}
		}
	}
	for(int i=0;i<=strlen(x);i++) delete [] c[i]; delete [] c;
	return a;
}

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

int lcs(string X,string Y){
  int c[1001][1001];
  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(){
  int q;cin>>q;
  while(q--){
    string a,b;cin>>a>>b;
    cout<<lcs(a,b)<<endl;
  }
  return 0;
}

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

using namespace std;

int q;
string A, B;

void findlongest() {
	int res[1001][1001];
	A = ' '+A ;
	B = ' '+B ;
	int l1 = A.size();
	int l2 = B.size();
	int max = 0;
	int j;
	for (int i = 0; i < l1; ++i) {
		for (j = 0; j < l2; ++j) {
			if (i == 0) {
				res[0][j] = 0;
			}
			else if (j == 0) {
				res[i][0] = 0;
			}
			else {
				if (A[i] == B[j]) {
					res[i][j] = res[i - 1][j - 1] + 1;
					if (max < res[i][j]) {
						max = res[i][j];
					}
				}
				else {
					if (res[i - 1][j] >= res[i][j - 1]) {
						res[i][j] = res[i - 1][j];
					}
					else {
						res[i][j] = res[i][j - 1];
					}
				}
			}
			//cout << res[i][j] << ' ';
		}
		//cout << endl;
	}

	cout << max << endl;
}

int main() {
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> A;
		cin >> B;
		findlongest();
	}
	return 0;
}