Go: package main

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

type Position struct {
	X int
	Y int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	for i := 0; i < n; i++ {
		strX := nextText(sc)
		strY := nextText(sc)
		fmt.Println(calcLcs(strX, strY))
	}
}

func calcLcs(strX, strY string) int {
	return lcs(strX, strY, Position{0, 0}, make(map[Position]int))
}

func lcs(strX string, strY string, position Position, memo map[Position]int) int {
	if position.X >= len(strX) || position.Y >= len(strY) {
		return 0
	}
	if v, ok := memo[position]; ok {
		return v
	}
	if strX[position.X] == strY[position.Y] {
		result := lcs(strX, strY, Position{position.X + 1, position.Y + 1}, memo)
		memo[position] = result + 1
		return memo[position]
	} else {
		result1 := lcs(strX, strY, Position{position.X + 1, position.Y}, memo)
		result2 := lcs(strX, strY, Position{position.X, position.Y + 1}, memo)
		var result int
		if result1 > result2 {
			result = result1
		} else {
			result = result2
		}
		memo[position] = result
		return result
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

C++: #include <iostream>
#include <string>
#include <utility>
using namespace std;
#define MAXQ 150
#define MAXL 1000

int main(){
    int n; cin >> n;
    pair<string, string> pairs[MAXQ];
    for(int i=0; i<n; ++i){
        cin >> pairs[i].first >> pairs[i].second;
    }
    
    for(int i=0; i<n; ++i){
        string str1, str2;
        str1 = pairs[i].first;
        str2 = pairs[i].second;
        int dp[MAXL][MAXL];
        for(int r=0; r<=str1.size(); ++r){
            dp[r][0] = 0;
        }
        for(int c=0; c<=str2.size(); ++c){
            dp[0][c] = 0;
        }
        for(int r=1; r<=str1.size(); ++r){
            for(int c=1; c<=str2.size(); ++c){
                int d = 0;
                if (str1[r-1] == str2[c-1]) d++;
                dp[r][c] = max(dp[r-1][c-1]+d, max(dp[r-1][c], dp[r][c-1]));
            }
        }
        cout << dp[str1.size()][str2.size()] << endl;
    }
}

C++: #include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
int main(){
    int n,dp[1001][1001];
    cin>>n;
    string x,y;
    rep(i,n){
        cin>>x>>y;
        rep(j,x.size()+1) rep(k,y.size()+1) dp[j][k]=0;
        rep(j,x.size()) rep(k,y.size()){
            if(x[j]==y[k]) dp[j+1][k+1]=max(max(dp[j][k]+1,dp[j+1][k]),dp[j][k+1]);
            else dp[j+1][k+1]=max(dp[j+1][k],dp[j][k+1]);
        }
        cout<<dp[x.size()][y.size()]<<endl;
    }
}

C++: //	created : 16/03/15
// 	author   : Rp7rf
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define INF 1e9


int main(void){
	int n;
	string s1,s2;
	cin>>n;
	int dp[1010][1010];
	rep(i,n){
		int ret = 0;
		cin>>s1>>s2;
		rep(i,s1.size()+1)dp[i][0] = 0;
		rep(j,s2.size()+1)dp[0][j] = 0;

		loop(i,1,s1.size()+1){
			loop(j,1,s2.size()+1){
				if(s1[i] == s2[j]){
					dp[i][j] = dp[i-1][j-1] + 1;
				}else{
					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				}
				ret = max(ret,dp[i][j]);
			}
		}
		cout<<ret<<endl;
	}
}

C++: #include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
#define F first
#define S second
#define MK make_pair
const ll E=1e17+7;
const ll MOD=1000000007;






int main(){
    ll q;
    cin>>q;
    while(q--){
        
        
    string a,b;
    cin>>a>>b;
    
    vector<set<ll>> w(300);
    vector<vector<ll>> dp(2000);
    for(int i=0;i<dp.size();i++){dp[i].resize(2000,E);}
    
    for(int i=0;i<b.size();i++){
        w[b[i]].insert(i);
    }
    
    ll mx=-1;
    
    for(int i=0;i<a.size();i++){
        for(int t=0;t<b.size()+100;t++){
            if(t==0 && *w[a[i]].begin()<dp[i][t]){
                dp[i+1][t]=*w[a[i]].begin();
            }
            else if(w[a[i]].upper_bound(dp[i][t-1])!=w[a[i]].end() && *w[a[i]].upper_bound(dp[i][t-1])<dp[i][t]){
                dp[i+1][t]=*w[a[i]].upper_bound(dp[i][t-1]);
                mx=max(mx,(ll)t+1);
            }
            else{dp[i+1][t]=dp[i][t];}
        }
    }
    cout<<mx<<endl;
        
        
    }
    
    return 0;
}

C++: #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

char a[1005],b[1005];
int n,c[1005][1005];

int lcs(){
    int n=strlen(a);
    int m=strlen(b);
    for(int i=0;i<n;i++) c[i][0]=0;
    for(int j=0;j<m;j++) c[0][j]=0;
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i]==b[j])
                c[i][j]=c[i-1][j-1]+1;
            else
                c[i][j]=max(c[i-1][j],c[i][j-1]);
            ans=max(c[i][j],ans);
        }
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        scanf("%s%s",a,b);
        printf("%d\n",lcs());
    }
    return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[1001][1001];

int main(){
	int i,n,j,k,la,lb;
	char a[1001],b[1001];
	scanf("%d",&n);
	while(n--){
		scanf("%s",a);
		scanf("%s",b);
		la = strlen(a);
		lb = strlen(b);
		for( i = 0; i < la; i++ ){
            for( j = 0; j < lb; j++ ){
                if( a[i] == b[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else {
                    if( dp[i+1][j] >= dp[i][j+1] ){
                        dp[i+1][j+1] = dp[i+1][j];
                    } else dp[i+1][j+1] = dp[i][j+1];
                }
            }
		}
		printf("%d\n",dp[la][lb]);
	}
}