Go: package main

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

const max int = 1000 + 1
var A [][]int

func lcs(x, y string) int {
	x = " " + x
	y = " " + y
	for i:=0;i<len(x); i++ {
		for j:=0;j<len(y); j++ {
			A[i][j] = 0
		}
	}
	for i:=1; i<len(x); i++ {
		for j:=1; j<len(y); j++ {
			if x[i] == y[j] {
				A[i][j] = A[i-1][j-1] + 1
			} else if A[i-1][j] > A[i][j-1] {
				A[i][j] = A[i-1][j]
			} else {
				A[i][j] = A[i][j-1]
			}
		}
	}
	return A[len(x)-1][len(y)-1]
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num 
}

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


func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	A = make([][]int, max)
	for i := range A {
		A[i] = make([]int, max)
	}
	n := nextInt(scanner)
	for i:=0; i<n; i++ {
		x := nextStr(scanner)
		y := nextStr(scanner)
		fmt.Printf("%d\n", lcs(x, y))
	}
}

C++: #include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define MAX 100000

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 ans=0;
  X= ' '+X;
  Y= ' '+Y;
  for(int i;i<=m;i++)c[i][0]=0;
  for(int j;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]);
      }
      ans=max(ans,c[i][j]);
    }
  
  }
  return ans;
}

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 1005

int table[MAX][MAX];

int LCS(string s, string t);

int main(){
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        string s,t; cin >> s >> t;
        cout << LCS(s, t) << endl;
    }
    return 0;
}

int LCS(string s, string t){
    int slen = s.length(), tlen = t.length();

    for(int i = 0; i <= slen; i++) table[0][i] = 0;
    for(int i = 0; i <= tlen; i++) table[i][0] = 0;
    for(int i = 0; i < slen; i++){
        for(int j = 0; j < tlen; j++){
            if(s[i] == t[j]){
                table[i+1][j+1] = table[i][j] +1;
            }else{
                table[i+1][j+1] = max(table[i][j+1], table[i+1][j]);
            }
        }
    }
    return table[slen][tlen];

}

C++: // Longest Common Subsequence

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
#define MAX 1001
int lcs[MAX][MAX] = {};
string x,y;

void make_lcs() {
	for (unsigned int i=0;i<=x.length();i++) {
	for (unsigned int j=0;j<=y.length();j++) {
	if (i!=0 && j!=0) {
	if (x[i] == y[j]) {
	lcs[i][j] = lcs[i-1][j-1] + 1;
	}
	else {
	lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
	}
	}
	}
	}
}

int main() {
	int n;
	cin >> n;
	for (int k=0;k<n;k++) {
	cin >> x >> y;
	make_lcs();
	cout << lcs[x.length()][y.length()] << 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];
int k;

int solve(int i, int j)
{
  if(dp[i][j] > 0)
    return dp[i][j];
  if(i >= str1.size() || j >= str2.size()){
    if(i < str1.size()){
      return solve(i + 1, k);
    }else{
      return 0;
    }
  }
  if(str1[i] == str2[j]){
    k = j + 1;
    int n, m = 0;
    for(int l = i + 1; l < str1.size(); l++){
      n = solve(l, j + 1);
      m = (n > m) ? n : m;
    }
    dp[i][j] = m + 1;
    return dp[i][j];
  }else{
    return solve(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);
    cout << solve(0, 0) << endl;
  }
}

C++: #include<iostream>
#include<stdio.h>
#include<string.h>
#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-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 <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1ll << 60;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int Q, DP[1005][1005];
string X, Y;

int Solve(){
  int N = X.length(), M = Y.length();
  fill((int*)DP, (int*)(DP + N + 1), 0);

  for (int i = 1; i <= N; i++){
    for (int j = 1; j <= M; j++){
      if (X[i - 1] == Y[j - 1]){
        DP[i][j] = DP[i - 1][j - 1] + 1;
      }else{
        DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
      }
    }
  }
  cout << DP[N][M] << endl;
  return 0;
}

int main(){
  cin >> Q;
  for (int i = 0; i < Q; i++){
    cin >> X >> Y;
    Solve();
  }

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int q;
char X[1000], Y[1000];
int dp[1001][1001];

int main(void) {

    scanf("%d", &q);

    for (int i = 0; i < q; ++i) {
        scanf("%s %s", X, Y);
        int xlen = strlen(X), ylen = strlen(Y);
        for (int x = 0; x < xlen; ++x) {
            for (int y = 0; y < ylen; ++y) {
                if (X[x] == Y[y]) {
                    dp[x + 1][y + 1] = dp[x][y] + 1;
                }
                else {
                    if (dp[x + 1][y] > dp[x][y + 1]) {
                        dp[x + 1][y + 1] = dp[x + 1][y];
                    }
                    else {
                        dp[x + 1][y + 1] = dp[x][y + 1];
                    }
                }
            }
        }
        printf("%d\n", dp[xlen][ylen]);
        memset(dp, 0, sizeof(int)*1001*1001);
    }
    printf("\n");
    return 0;
}