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++: // Longest Common Subsequence

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
#define MAX 1001
int lcs[MAX][MAX] = {};
string x,y;

void make_lcs() {
	for (unsigned int i=0;i<=x.length();i++) {
	for (unsigned int j=0;j<=y.length();j++) {
	if (i!=0 && j!=0) {
	if (x[i] == y[j]) {
	lcs[i][j] = lcs[i-1][j-1] + 1;
	}
	else {
	lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
	}
	}
	}
	}
}

int main() {
	int n;
	cin >> n;
	for (int k=0;k<n;k++) {
	cin >> x >> y;
	make_lcs();
	cout << lcs[x.length()][y.length()] << endl;
	}
	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 0;
    }
  }
  if(str1[i] == str2[j]){
    k = j + 1;
    int n, m = 0;
    for(int l = i + 1; l < str1.size(); l++){
      n = solve(l, j + 1);
      m = (n > m) ? n : m;
    }
    dp[i][j] = m + 1;
    return dp[i][j];
  }else{
    return solve(i, j + 1);
  }
}
  
int main()
{
  int q;
  cin >> q;
  cin.ignore();
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    fill(&dp[0][0], &dp[1001][0], -1);
    cout << solve(0, 0) << endl;
  }
}

C++: #include<iostream>
#include<stdio.h>
#include<string.h>
#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.size();
    int n=Y.size();
    int maxl=0;
    X=" "+X;
    Y=" "+Y;
    for(int i=0;i<=m;i++)c[i][0]=0;
    for(int j=0;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 <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1ll << 60;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int Q, DP[1005][1005];
string X, Y;

int Solve(){
  int N = X.length(), M = Y.length();
  fill((int*)DP, (int*)(DP + N + 1), 0);

  for (int i = 1; i <= N; i++){
    for (int j = 1; j <= M; j++){
      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[N][M] << endl;
  return 0;
}

int main(){
  cin >> Q;
  for (int i = 0; i < Q; i++){
    cin >> X >> Y;
    Solve();
  }

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int q;
char X[1000], Y[1000];
int dp[1001][1001];

int main(void) {

    scanf("%d", &q);

    for (int i = 0; i < q; ++i) {
        scanf("%s %s", X, Y);
        int xlen = strlen(X), ylen = strlen(Y);
        for (int x = 0; x < xlen; ++x) {
            for (int y = 0; y < ylen; ++y) {
                if (X[x] == Y[y]) {
                    dp[x + 1][y + 1] = dp[x][y] + 1;
                }
                else {
                    if (dp[x + 1][y] > dp[x][y + 1]) {
                        dp[x + 1][y + 1] = dp[x + 1][y];
                    }
                    else {
                        dp[x + 1][y + 1] = dp[x][y + 1];
                    }
                }
            }
        }
        printf("%d\n", dp[xlen][ylen]);
        memset(dp, 0, sizeof(int)*1001*1001);
    }
    printf("\n");
    return 0;
}

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

using ll = long long;
using Field = vector<vector<ll>>;
using Graph = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VC = vector<char>;
using PI = pair<int, int>;

#define FOR(i, s, n) for (int i = s; i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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

int q;


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> q;

    REP(_, q) {

        string A, B;
        vector<vector<int>> dp(1010, vector<int>(1010));

        cin >> A >> B;

        for (int i = 0; i < A.size(); i++) {
            if (A[i] == B[0]) dp[i][0] = 1;
            chmax(dp[i+1][0], dp[i][0]);
        }
        for (int i = 0; i < B.size(); i++) {
            if (A[0] == B[i]) dp[0][i] = 1;
            chmax(dp[0][i + 1], dp[0][i]);
        }
        
        for (int i = 1; i < A.size(); i++) {
            for (int j = 1; j < B.size(); j++) {
                if (A[i] == B[j]) {
                    chmax(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    chmax(dp[i][j], dp[i][j-1]);
                    chmax(dp[i][j], dp[i-1][j]);
                }
            }
        }



        cout << dp[A.size() - 1][B.size() - 1] << endl;


    }


    

    return 0;
}

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.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;
}