Go: package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var q int
var X, Y string

func lcs(X, Y string) int {
	lenX := len(X)
	lenY := len(Y)
	dp := make([][]int, lenX+1)
	for i := 0; i < lenX+1; i++ {
		dp[i] = make([]int, lenY+1)
	}

	res := 0
	for i := 1; i < lenX+1; i++ {
		for j := 1; j < lenY+1; j++ {
			if X[i-1] == Y[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
			//fmt.Println(dp)
			res = maxInt(res, dp[i][j])
		}

	}
	return res
}

func main() {
	sc.Split(bufio.ScanWords)
	q = nextInt()

	for i := 0; i < q; i++ {
		X = nextStr()
		Y = nextStr()

		fmt.Println(lcs(X, Y))
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(n,a) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265


void f(){
  string x,y;
  cin>>x>>y;
  int dp[1100][1100]={};
  
  rep(i,x.length()+1){
    rep(j,y.length()+1){
      if(i==0||j==0) continue;
      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[(int)x.length()][(int)y.length()]<<endl;
}


int main(){
  int q;
  cin>>q;
  while(q--){
    f();
  }
}

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

int main() {
  int q;
  cin >> q;
  for (int i=0;i<q;++i) {
    string str1,str2;
    cin >> str1 >> str2;
    int size1 = str1.size();
    int size2 = str2.size();
    int matrix[size1+1][size2+1];
    for (int j=0;j<=size1;++j)
      matrix[j][0] = 0;
    for (int j=0;j<=size2;++j)
      matrix[0][j] = 0;
    for (int j=0;j<=size1;++j) {
      for (int k=0;k<=size2;++k) {
	if (j<=0||k<=0) {
	  matrix[j][k] = 0;
	}
	else if (str1[k]==str2[j]) {
	  matrix[j][k] = 1 + matrix[j-1][k-1];
	}
	else {
	  matrix[j][k] = max(matrix[j][k-1],matrix[j-1][k]);
	}
      }
    }
    cout << matrix[size1][size2] << endl;
  }
}

int max(int a,int b) {
  if (a>b)
    return a;
  else
    return b;
}

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


int main(int argc, char *argv[]){
  int n;
  cin >> n;
  for (int r = 0; r < n; r++) {

    string x, y;
    cin >> x >> y;
    string dp[y.length() + 1][x.length() + 1];

    for (int i = 0; i < y.length(); i++) {
      for (int j = 0; j < x.length(); j++) {
        if(y[i] == x[j]){
          dp[i + 1][j + 1] = dp[i][j] + y[i];
        }else{
          dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
      ans = max(ans, (int)dp[y.length()][i].length());
    }
    std::cout << ans << std::endl;
  }
  return 0;
}

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

int lcs(string x, string y) {
	int m = x.size();
	int n = y.size();
	int c[1001][1001];
	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;
				if (c[i][j] > maxl) {
					maxl = c[i][j];
				}
			}
			else {
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
			}
		}
	}
	return maxl;
}

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

C++: #include<bits/stdc++.h>
using namespace std;
int main(){
	int f[1001][1001];
	string s,s1;
	int t,n,m;
	cin>>t; 
	while (t--){
		  memset(f,0,sizeof(f));
		  cin>>s>>s1; 
		  n=s.length(); m=s1.length();
		  s='0'+s; s1='0'+s1;
		  for (int i=1; i<=n; i++)
		      for (int j=1; j<=m; j++){
		      	  if (s[i]==s1[j]){
		      	     f[i][j]=f[i-1][j-1]+1;	
				  }
				  else{
				  	 f[i][j]=max(f[i][j-1],f[i-1][j]);
				  }
			  }
		  cout<<f[n][m]<<endl;
	}
	return 0;
}

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

void Ics(char *X, char *Y)
{
   int c[1000][1000];
   int m, n, i, j;

   m = strlen(X);
   n = strlen(Y);

   for ( i = 1; i <= m, i++ ) {
      c[i][0] = 0;
   }
   for ( j = 0; j <= n; j++ ) {
      c[0][j] =0;
   }

   for ( i = 1; i <= m; i++ ) {
      for ( j = 1; j <=n; j++ ) {
         if ( X[ i - 1 ] == Y[ j - 1] ) {
            c[ i ][ j ] = c[ i - 1 ][ j - 1 ] + 1;
         } else if ( c[ i - 1 ][ j ] >= c[ i ][ j - 1 ] ){
            c[ i ][ j ] = c[ i - 1 ][ j ];
         } else {
            c[ i ][ j ] = c[ i ][ j - 1 ];
         }
      }
   }
   printf("%d\n", c[ m ][ n ]);
}
     
int main()
{
   int q, i;
   char X[1000], Y[1000];

   scanf("%d", &q);
   for ( i = 0; i < q; i++ ) {
      scanf("%s%s", X, Y);
      Ics(X, Y);
   }
   return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
using namespace std;
void input(string &x,string &y){
	cin>>x>>y;
}
int lcs(string x,string y){
	vector<vector<int>> tb(vector<vector<int>>((int)x.size()+1,vector<int>(y.size()+1,0)));
	for(int i=1;i<(int)x.size()+1;i++){
		for(int j=1;j<(int)y.size()+1;j++){
			if(x[i]==y[j])  tb[i][j]=tb[i-1][j-1]+1;
			else tb[i][j]=max(tb[i-1][j],tb[i][j-1]);
		}
	}
	return tb[(int)x.size()][(int)y.size()];
}
int main(){
	int q;
	cin>>q;
	string x,y;
	for(int i=0;i<q;i++){
		input(x,y);
		cout<<lcs(x,y)<<endl;
	}
	return 0;
}

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



int lcs(string X,string Y){
	
	int c[720][720];
int m = X.size();
int n = Y.size();
int max1 = 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]);
		}
		max1 = max(max1,c[i][j]);
		}
	} 
	return max1;
}



int main(){
	int q;
	int a[500];
	string s1,s2;
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>s1>>s2;
		a[i] = lcs(s1,s2);
	}
	for(int i=0;i<q;i++){
		cout<<a[i]<<endl;
	}
	return 0;
}

C++: #include<iostream>
#include<string>
#define lth 1000

using namespace std;

int main()
{
	int n, L[1000][1000], Lmax = 0, *save;
	string Xi[lth], Yi[lth];
	cin >> n;
	save = new int[n];
	for (int k = 0; k < n; k++)
	{
		Lmax = 0;
		string X, Y;
		cin >> X >> Y;
		for (int i = 0; i <= X.length(); i++)
		{
			if (i != 0)
				Xi[i] = X.substr(0, i );
		}
		for (int i = 0; i <= Y.length(); i++)
		{
			if (i != 0)
				Yi[i] = Y.substr(0, i );
		}
		for (int i = 0; i <= X.length(); i++)
			for (int j = 0; j <= Y.length(); j++)
			{
				if (i == 0 || j == 0)
					L[i][j] = 0;
				else if (Xi[i][i - 1] == Yi[j][j - 1])
				{
					L[i][j] = L[i - 1][j - 1] + 1;
				}
				else
				{
					L[i][j] = (L[i][j - 1] > L[i - 1][j]?L[i][j - 1] : L[i - 1][j]);
				}
				if (Lmax < L[i][j]) Lmax = L[i][j];
			}
		save[k] = Lmax;
	}
	for (int i = 0; i < n; i++)
		cout << save[i] << endl;
	//system("pause");
}