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

using namespace std;

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

        int len[1001][1001] = {};
        for (int s = 1; s <= X.length(); s++) {
            for (int t = 1; t <= Y.length(); t++) {
                if (X[s-1] == Y[t-1]) len[s][t] = 1 + len[s-1][t-1];
                else len[s][t] = max(len[s-1][t], len[s][t-1]);
            }
        }
        cout<<len[X.length()][Y.length()]<<endl;
    }
}

C++: #include <iostream>
using namespace std;
#define MAX 2000

int c[MAX][MAX];
int lcs(string x, string y)
{
    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 if(c[i-1][j]>=c[i][j-1])
                c[i][j] = c[i-1][j];
            else
                c[i][j] = c[i][j-1];
        }
    }
}
int main()
{
    int n, t;
    string s1, s2;
    cin >> n;
    while(n--)
    {
        cin >> s1 >> s2;
        lcs(s1,s2);
        cout << c[s1.size()][s2.size()] << endl;
    }
    return 0;
}

C++: #include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

ll dp[1010][1010];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	ll q;
	cin >> q;
	while (q--) {
		string x, y;
		cin >> x >> y;
		memset(dp, 0, sizeof(dp));
		
		REP(i, x.size()) {
			REP(j, y.size()) {
				if (x[i] == y[j]) {
					chmax(dp[i + 1][j + 1], dp[i][j] + 1);
				}
				chmax(dp[i + 1][j + 1], dp[i + 1][j]);
				chmax(dp[i + 1][j + 1], dp[i][j + 1]);
			}
		}

		cout << dp[x.size()][y.size()] << endl;
	}

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define ALL(x) x.begin(),x.end()
typedef pair<int, int> P;
typedef long long ll;

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

// int solve(int i, int j) {
//
//     if (dp[i][j] >= 0) {
//         return dp[i][j];
//     }
//
//     int res;
//     if (i >= n || j >= m) {
//         res = 0;
//     }
//     else if (s[i] == t[j]) {
//         res = solve(i+1, j+1) + 1;
//     }
//     else {
//         res = max(solve(i+1, j), solve(i, j+1));
//     }
//     return dp[i][j] = res;
// }

int main() {
    cin >> N;
    while (N--) {
        cin >> s >> t;
        int n = s.size(), m = t.size();
        fill(dp[0], dp[1001], 0);
        for (int i=0;i<n;++i) {
            for (int j=0;j<m;++j) {
                if (s[i] == t[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]);
                }
            }
        }
        cout << dp[n][m] << endl;
    }
}

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

int N,len1,len2;
string seq1,seq2;
int dp[1000][1000];

int main() {
	cin >> N;
	for (int M=0; M<N; M++){
		cin >> seq1 >> seq2;
		len1 = seq1.length();
		len2 = seq2.length();
		for (int i=1; i<=len1; i++){
			for (int j=1; j<=len2; j++){
				if (seq1[i-1] == seq2[j-1]){
					dp[i][j] = dp[i-1][j-1] + 1;
				}else if (dp[i][j-1] > dp[i-1][j]){
					dp[i][j] = dp[i][j-1];
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		cout << dp[len1][len2] << endl;
	}
	
	return 0;
}

C++: #include<iostream>
#include<string>

using namespace std;

#if 0
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2065462#1
#endif

int n;
string a, b;
string x[10000], y[10000];




int main(){
  cin >> n;
  while(n != 0){
    n = n -1;
    int longest[1000][1000];
    cin >> a;
    cin >> b;
    a = ' ' + a;
    b = ' ' + b;
    int mm = 0;
    /*
    for(int i = 0; i < a.size(); ++i){
      for(int j = 0; j < b.size(); ++j){
        
        x[i] = a;
        y[j] = b;
      }
    }
    */
   //longest[0][0] =0;
   for(int i = 1; i <= a.size(); ++i){
     longest[i][0] = 0;
    }
   for(int j = 1; j <= b.size(); ++j){
     longest[0][j] = 0;
   }
    for(int i = 1; i <= a.size(); ++i){
      for(int j = 1; j <= b.size(); ++j){
        
        /*
        if(i <= 0 || j <=0){
          longest[i][j] = 0;
        }
        */
        if(a[i] == b[j]){
          longest[i][j] = 1 + longest[i-1][j - 1];
        }
        else{
          longest[i][j] = max(longest[i][j-1], longest[i-1][j]);
        }
        mm = max(mm, longest[i-1][j-1]);
      }
    }
    //cout << a[1] << endl;
    cout << mm << endl;
  }
}

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

using namespace std;

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

        int len[1001][1001] = {};
        for (int s = 1; s <= X.length(); s++) {
            for (int t = 1; t <= Y.length(); t++) {
                if (X[s] == Y[t]) len[s][t] = 1 + len[s-1][t-1];
                else len[s][t] = max(len[s-1][t], len[s][t-1]);
            }
        }
        cout<<len[X.length()][Y.length()]<<endl;
    }
}

C++: #include <iostream>
#include <string>
#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.length();
	int n = Y.length();
	int maxlen = 0;
	X = ' ' + X;
	Y = ' ' + Y;
	for (int i = 0; i < m + 1; i++)c[i][0] = 0;
	for (int j = 1; j < n + 1; j++)c[0][j] = 0;

	for (int i = 1; i < m + 1; i++) {
		for (int j = 1; j < n + 1; 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]);
			}
			maxlen = max(maxlen, c[i][j]);
		}
	}
	return c[m][n];
}

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