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 <cmath>
#include <string>

using namespace std;

int main(int argc, char const* argv[])
{
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
			string a, b;
			cin >> a;
			cin >> b;
			int **dp = new int*[a.size() + 1];
			for(int j = 0; j < a.size() + 1; j++){
					dp[j] = new int[b.size() + 1];
			}
			for(int j = 0; j <= a.size(); j++)dp[j][0] = 0;
			for(int j = 0; j <= b.size(); j++)dp[0][j] = 0;
			for(int j = 0; j < a.size(); j++){
					for(int k = 0; k < b.size(); k++){
							if(a[j] == b[k])dp[j + 1][k + 1] = dp[j][k] + 1;
							else{
									dp[j + 1][k + 1] = max(dp[j][k], dp[j+1][k]);
									dp[j + 1][k + 1] = max(dp[j + 1][k + 1], dp[j][k+1]);
							}
					}
			}
			cout << dp[a.size()][b.size()] << endl;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
#include<limits.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define MAX 1001

vector<vector<int>> init_c(MAX, vector<int>(MAX, -1));
vector<vector<int>> c(MAX, vector<int>(MAX, -1));
string a, b;

int lcs(int i, int j){
    if(i == 0 || j == 0){
        c.at(i).at(j) = 0;

    }else if(c.at(i).at(j) != -1){
        return c.at(i).at(j);

    }else if(a.at(i - 1) == b.at(j - 1)){
        c.at(i).at(j) = lcs(i-1, j-1) + 1;

    }else{
        c.at(i).at(j) = max(lcs(i, j - 1), lcs(i - 1, j));
    }
    // cout << i << " " << j << " " << c.at(i).at(j) << endl;
    
    return c.at(i).at(j);
}

int main(){
    int q; cin >> q;
    rep(i, q){
        c = init_c;
        cin >> a; cin >> b;
        cout << lcs(a.size(), b.size()) << endl;
    }

}

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

string a, b;
int N, M;
vector<vector<int> > dp;

int dfs(int n, int m) {
  if ( n == N || m == M ) return 0;
  if ( dp[n][m] >= 0 ) return dp[n][m];
  
  int ret = 0;
  //cout << n << " " << m << " " << cnt << endl;
  if ( a[n] == b[m] ) ret = dfs(n+1, m+1)+1;
  else ret = max(ret, max(dfs(n+1, m), dfs(n, m+1)));

  return dp[n][m] = ret;
}

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

  while ( q-- ) {
    cin >> a >> b;
    N = a.size();
    M = b.size();
    dp = vector<vector<int> >(N+1, vector<int>(M+1, -1));    
    cout << dfs(0, 0) << endl;
  }
  
  return 0;
}

C++: #include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;

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

    int q;
    cin >> q;
    vector<int> res(q);

    rep(_, q){
        string x, y;
        cin >> x >> y;
        if(y.size() > x.size()) swap(x, y);

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

        vector<vector<int>> dp(n, vector<int>(m, 0));
        if(x[0] == y[0]) dp[0][0] = 1;
        else dp[0][0] = 0;

        rep1(i, m){
            if(y[0] == x[i]) dp[0][i] = 1;
            else dp[0][i] = dp[0][i-1];
        }

        rep1(i, n){
            dp[i][0] = dp[i-1][0];
            if(y[i] == x[0]) dp[i][0] = 1;

            rep1(j, m){
                if(y[i] == x[j]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }

        // rep(i, n){
        //     rep(j, m) cout << dp[i][j] << " ";
        //     cout << endl;
        // }

        cout << dp[n-1][m-1] << endl;
        
    }

    return 0;
}

C++: #include <bits/stdc++.h>
#include <cmath>

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef long long ll;
typedef long long ll;
//typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX / 100;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("~/Downloads/02.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
const double PI = 3.14159265358979323846;

typedef pair<ll, ll> P;


string to_upper(string str) {
    int diff = 'a' - 'A';
    for (int i = 0; i < str.size(); i++) {
        char c = str[i];
        if ('A' <= c && c <= 'Z') {
            c += diff;
            str[i] = c;
        }
    }
    return str;
}


int main() {

    int n;
    cin >> n;

    rep(k, n) {

        string s1, s2;
        cin >> s1 >> s2;
        vector<vector<pair<int, pair<int, int> > > > dp(s1.size() + 1,
                                                        vector<pair<int, pair<int, int> > >(s2.size() + 1));
        for (int i = 0; i <= s1.size(); i++) {
            for (int j = 0; j <= s2.size(); j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = make_pair(0, make_pair(-1, -1));
                } else {
                    dp[i][j] = dp[i][j - 1];
                    if (dp[i][j].first < dp[i - 1][j].first) {
                        dp[i][j] = dp[i - 1][j];
                    }
                    if (s1[i - 1] == s2[j - 1] && dp[i][j].first < dp[i - 1][j - 1].first + 1) {
                        dp[i][j] = make_pair(dp[i - 1][j - 1].first + 1, make_pair(i - 1, j - 1));
                    }
                }
            }
        }
        vector<char> subseq_stack;
        for (int i = s1.size(), j = s2.size(); i > 0 && j > 0;) {
            pair<int, int> next = dp[i][j].second;
            //make_pair(i,j) = next;
            i = next.first;
            j = next.second;
            if (i < 0 || j < 0) break;
            subseq_stack.push_back(s1[i]); // s1[i] == s2[j]
        }
        cout << subseq_stack.size() << endl;
    }
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
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 = 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]);
        }
        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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxx = 1010;
int c[maxx][maxx];

int lcs(char s1[],char s2[]) {
	int m = strlen(s1), n = strlen(s2);
	for (int i = 1; i <= m; i++)
		c[i][0] = 0;
	for (int i = 1; i <= n; i++)
		c[0][i] = 0;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; 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]);
		}
	}
	return c[m][n];
}
int main()
{
	char s1[maxx], s2[maxx];
	int t;
	scanf("%d", &t);
	getchar();
	for (int i = 0; i < t; i++) {
		scanf("%s %s", s1, s2);
		printf("%d\n", lcs(s1,s2));
	}

	return 0;
}