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<cstdio>
#include<cstring>
#include<algorithm>
#include<string>

using namespace std;

const int maxn=1010;
int c[maxn][maxn];
string s1,s2;

int lcs(int x,int y)
{
	for(int i=1;i<=x;i++)c[i][0]=0;
	for(int j=1;j<=y;j++)c[0][j]=0;
	s1=' '+s1;
	s2=' '+s2;//插入空格
	int maxl=0; 
	for(int i=1;i<=x;++i){
		for(int j=1;j<=y;++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]);
			}
			maxl=max(maxl,c[i][j]);//每次取最大值并更新 
		}
	}
	return maxl;
}

int main()
{
	int t;
	cin>>t;
	while(t--){
		memset(c,0,sizeof(c));
		cin>>s1>>s2;
		int len1=s1.length();
		int len2=s2.length();
		int ans=lcs(len1,len2);
		cout<<ans<<endl;
	}
	return 0;	
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

void chmax(int &a, int b) {
  if (a < b) a = b;
}

int main() {

  int q;
  cin >> q;
  while (q--) {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    rep(i, n) rep(j, m) {
      chmax(dp[i + 1][j + 1], dp[i + 1][j]);
      chmax(dp[i + 1][j + 1], dp[i][j + 1]);
      if (s[i] == t[j]) { chmax(dp[i + 1][j + 1], dp[i][j] + 1); }
    }
    cout << dp[n][m] << endl;
  }

  return 0;
}

C++: #include<iostream>
#include<string>
int main()
{
  int n;
  int an[1000];
  int l=0;
  std::cin>>n;
  std::string x;
  std::string y;
  int ans[1000][1000];
  int j,k;
  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<1000;j++){
      for(int k=0;k<1000;k++){
	ans[j][k]=0;
      }
    }
    for(int j=0;j<x.size();j++){
      for(int k=0;k<y.size();k++){
	if(x[j]==y[k]){
	  ans[j][k]=ans[j-1][k-1]+1;
	}else{
	  if(ans[j][k-1]>ans[j-1][k]){
	    ans[j][k]=ans[j][k-1];
	  }else{
	    ans[j][k]=ans[j-1][k];
	  }
	}
      }
    }
    std::cout<<ans[x.size()-1][y.size()-1]<<'\n';  
  }
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int solve(char* x,char* y){
    int n=strlen(x),m=strlen(y);
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    for(int i=0;i<n+1;i++){
        if(!i)continue;
        for(int j=0;j<m+1;j++){
            if(!j)continue;
            if(x[i-1]==y[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    return dp[n][m];
}
int main(){
    int q;scanf("%d",&q);
    while(q--){
        char x[1000],y[1000];
        scanf("%s%s",x,y);
        printf("%d\n",solve(x,y));
    }
    return 0;
}

C++: #include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=1e9;
int dp[1001][1001];
int main(){
      string s,t;
      int n;
      cin>>n;
      while(n--){
            cin>>s>>t;
            memset(dp,0,sizeof(dp));
            REP(i,s.size()){
                  REP(j,t.size()){
                        if(s[i]==t[j])dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
                        else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                  }
            }
            cout<<dp[s.size()][t.size()]<<endl;
      }
}

C++: #include <bits/stdc++.h>
#include<algorithm>
#define int long long
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1000000000000
int MOD=1000000007;
int n;
int dp[1001][1001];
signed main() {
cin>>n;
rep(ii,n){
  rep(p,1001){
    rep(q,1001){
      dp[p][q]=0;
    }
  }
  string x,y;
  cin>>x>>y;
  rep(i,x.size()){
    rep(j,y.size()){
      if(x[i]==y[j]){dp[i+1][j+1]=1+dp[i][j];}
      else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
    }
  }
cout<<dp[x.size()][y.size()]<<endl;
 }
}

C++: #include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;

ll N;

void lcs(string a, string b){
    int DP[a.size()+1][b.size()+1]={{0}};
    for(int i=0;i<=a.size();i++) DP[i][0]=0;
    for(int i=0;i<=b.size();i++) DP[0][i]=0;
    for(int i=1;i<=a.size();i++){
        for(int j=1;j<=b.size();j++){
            if(a[i-1]==b[j-1]) DP[i][j] = DP[i-1][j-1] + 1;
            else DP[i][j] = max(DP[i][j-1], DP[i-1][j]);
            //cout << " " << DP[i][j];
        }
        //cout << endl;
    }
    cout << DP[a.size()][b.size()] << endl;
    return;
}

signed main(){
    cin >> N;
    for(int i=0;i<N;i++){
        string A, B;
        cin >> A >> B;
        lcs(A, B);
    }
    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 1;
    }
  }
  if(str1[i] == str2[j]){
    k = j + 1;
    dp[i][j] = solve(i + 1, j + 1);
    return dp[i][j] + 1;
  }else{
    return solve(i, j + 1);
  }
}

int main()
{
  int q, n, ans = 0;
  cin >> q;
  cin.ignore();
  fill(&dp[0][0], &dp[1001][0], -1);
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    REP(i, str1.size()){
      n = solve(i, 0) - 1;
      ans = (n > ans) ? n : ans;
    }
  }
  cout << ans << endl;
}