Go: // AOJ ALDS1_10_C: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

package main

import (
	"fmt"
)

func main() {
	var dataNum int
	var s1, s2 string

	fmt.Scanf("%d", &dataNum)

	for i := 0; i < dataNum; i++ {
		fmt.Scanf("%s", &s1)
		fmt.Scanf("%s", &s2)

		lcs := make([][]int, len(s1)+1)
		for j := 0; j < len(s1)+1; j++ {
			lcs[j] = make([]int, len(s2)+1)
		}

		for m, vs1 := range s1 {
			for n, vs2 := range s2 {
				if vs1 == vs2 {
					lcs[m+1][n+1] = lcs[m][n] + 1
				} else if lcs[m+1][n] > lcs[m][n+1] {
					lcs[m+1][n+1] = lcs[m+1][n]
				} else {
					lcs[m+1][n+1] = lcs[m][n+1]
				}
			}
		}

		// Answer
		fmt.Println(lcs[len(s1)][len(s2)])
	}
}

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

#define int long long

#define rep(i,s,n) for(int i = s;i<n;i++)
/*#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint>PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;
int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};*/


int dp[1010][1010];
int N;
string s,t;

void lcs(string s,string t){
	memset(dp,0,sizeof(dp));
	int n=s.size(),m=t.size();
	rep(i,0,n){
		rep(j,0,m){
			if(s[i]==t[j]){
				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[n][m]<<endl;
};
signed main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
    cin>>N;
    rep(i,0,N){
        cin>>s>>t;
        lcs(s,t);
    }
   
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}

C++: #define PI 3.14159265359
#define INF 2000000000
#define MAX 500000
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;

void LCS(string X,string Y){
 int c[1002][1002];
 int n=X.length(),m=Y.length();
 for(int i=0;i<=max(n,m);i++){
     c[i][0]=c[0][i]=0;
 }
 for(int i=1;i<=n;i++){
     for(int j=1;j<=m;j++){
         if(X[i-1]==Y[j-1])
           c[i][j]=c[i-1][j-1]+1;
         else{
           c[i][j]=max(c[i][j-1],c[i-1][j]);
         }
     }
 }
 cout<<c[n][m]<<endl;
}

int main(){
    int q;
    cin>>q;
    string X,Y;
    for(int i=0;i<q;i++){
        cin>>X>>Y;
        LCS(X,Y);
    }
}

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

int main() {
  int q; cin >> q;
  string A, B;
  for (int i=0; i<q; i++) {
    cin >> A >> B;
    vector<vector<int>> LCS(A.length()+1, vector<int>(B.length()+1,0));
    int ans=0;
    for (int j=0; j<A.length(); j++) {
      for (int k=0; k<B.length(); k++) {
        if(A[j]==B[k]) LCS[j+1][k+1]=LCS[j][k]+1;
        else LCS[j+1][k+1]=max(LCS[j][k+1],LCS[j+1][k]);
        ans = max(ans, LCS[j+1][k+1]);
      }
    }
    cout << ans << "\n";
  }
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void){
	int q;
	cin >> q;
	rep(u, q){
		string S, L;
		cin >> S >> L;
		int dp[1002][1002];
		rep(i, S.size())
			rep(j, L.size()){
				if(S[i] == L[j]){
					dp[i+1][j+1] = dp[i][j]+1;
				}else{
					dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
				}
			}
			FIN(dp[S.size()][L.size()]);
	}

	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include<string.h>
using namespace std;
int LCS(char *x,char *y);
char x[1001], y[1001];
int lcs[1001][1001];
int main()
{
	int q,i,j;

	cin >> q;
	for (i = 0; i < q; i++) {
		cin >> x;
		cin >> y;
		cout << LCS(x, y) << endl;
	}
}

int LCS(char *x, char *y)
{
	int i, j;
	int len_x, len_y;
	len_x = strlen(x);
	len_y = strlen(y);
	
	for (i = 0; i < len_x; i++) {
		if (x[0] == y[i]) {
			lcs[0][i] = 1;
		}
		else {
			lcs[0][i] = 0;
		}
	}
	for (i = 0; i < len_x; i++) {
		if (x[i] == y[0]) {
			lcs[i][0] = 1;
		}
		else {
			lcs[i][0] = 0;
		}
	}

	for (i = 0; i < len_x; i++) {
		for (j = 0; j < len_y; j++) {
			if (x[i] == y[j]) {
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
				//printf("lcs[%d][%d]=%d\n", i, j, lcs[i - 1][j - 1] + 1);
			}
			if (x[i] != y[j]) {
				lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
				//printf("lcs[%d][%d]=%d\n", i, j, max(lcs[i - 1][j], lcs[i][j - 1]));
			}
		}
	}
	//cout << endl;

	for (i = 0; i < len_x; i++) {
		for (j = 0; j < len_y; j++) {
			//printf("%d ", lcs[i][j]);
		}
		//cout << endl;
	}
	//cout << "len_x=" << len_x << endl << "len_y=" << len_y << endl;
			
	return lcs[len_x-1][len_y-1];
}

C++: #define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

const int N = 1001;

int lcs(string x, string y)
{
	vector<vector<int>> c(N, vector<int>(N));

	int m = x.size();
	int n = y.size();

	int maxl = 0;

	x = " " + x;
	y = " " + y;

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (x.at(i) == y.at(j))
			{
				c.at(i).at(j) = c.at(i - 1).at(j - 1) + 1;
			}
			else
			{
				c.at(i).at(j) = max(c.at(i).at(j - 1), c.at(i - 1).at(j));
			}

			maxl = max(maxl, c.at(i).at(j));
		}
	}

	return maxl;
}

int main()
{
	int n;
	for (cin >> n; n--;)
	{
		string s0, s1;
		cin >> s0 >> s1;

		cout << lcs(s0, s1) << endl;
	}
}

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

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        string X, Y;
        cin >> X >> Y;
        vector<vector<int>> dp(X.size() + 1);
        for (int j = 0; j < dp.size(); j++)
        {
            dp[j].resize(Y.size() + 1, 0);
        }

        int res = 0;
        for (int j = 0; j < X.size(); j++)
        {
            for (int k = 0; k < Y.size(); k++)
            {
                if (X[j] == Y[k])
                {
                    dp[j + 1][k + 1] = dp[j][k] + 1;
                    res = max(res, dp[j + 1][k + 1]);
                }
                else
                {
                    dp[j + 1][k + 1] = max(dp[j][k + 1], dp[j + 1][k]);
                }

                // cout << "########## (" << j << ", " << k << ") ##########" << endl;
                // cout << dp[j + 1][k + 1] << endl;
            }
        }

        cout << res << endl;
    }

    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int main(){
  int q;
  cin>>q;
  for(int cn=0;cn<q;cn++){
    string x,y;
    cin>>x>>y;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=x.size();i++){
      for(int j=1;j<=y.size();j++){
	if(x[i-1]==y[j-1])dp[i][j]=dp[i-1][j-1]+1;
	dp[i][j]=max(dp[i-1][j],dp[i][j]);
	dp[i][j]=max(dp[i][j-1],dp[i][j]);
      }
    }
    cout<<dp[x.size()][y.size()]<<endl;
  }
  return 0;
}