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<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int,int> pii;

vector<pii> P;

string s,t,rev;

const int MAX_N = 1001;

int dp[MAX_N][MAX_N];

void trace(int i,int j){
	if(dp[i][j] == dp[i-1][j] && dp[i][j] == dp[i][j-1]){
		trace(i-1,j-1);	//??????????§????
	}else if(dp[i][j] == dp[i-1][j]){
		trace(i-1,j);	//???????§????
	}else if(dp[i][j] == dp[i][j-1]){
		trace(i,j-1);	//???????§????
	}else{
		rev += s[i-1];
		if(dp[i-1][j-1] == 0){
			return;
		}
		trace(i-1,j-1);	//??????????§????
	}
}
int main()
{
	string com;
	int n;
	cin >> n;
	for(int l=0;l<n;l++){
	cin >> s;
	cin >> t;
	for(int i=0;i<=s.length();i++){
		dp[i][0] = 0;
	}
	for(int i=0;i<=t.length();i++){
		dp[0][i] = 0;
	}
	for(int i=1;i<=s.length();i++){
		for(int j=1;j<=t.length();j++){
			if(s[i-1] == t[j-1]){
				dp[i][j] = dp[i-1][j-1]+1;
			}else{
				dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
			}
		}
	}
	printf("%d\n",dp[s.length()][t.length()]);
	}
	/*
	trace(s.length(),t.length());
	for(int i=rev.length();i>0;i--){
		com += rev[i-1];
	}
	cout << com << "\n";	//????????±?????¨???????????????????????????
	*/
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const int MOD = 1e9+7;


#define REP(i, N) for (int i = 0; i < (N); i++)
#define REPP(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((int)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<int>>

using namespace std;
string x,y;
int LCS[1002][1002];


int searchLCS(int now_x, int now_y){
    // cout << now_x << " : " << now_y << endl;
    if(LCS[now_x+1][now_y+1] > 0) return LCS[now_x+1][now_y+1];
    if(now_x < 0 || now_y < 0) return LCS[now_x+1][now_y+1] = 0;
    if(x[now_x] == y[now_y]){
        return LCS[now_x+1][now_y+1] = searchLCS(now_x-1,now_y-1)+1;
    }else if(now_x >= 0 && now_y >= 0){
        return LCS[now_x+1][now_y+1] = max(searchLCS(now_x-1,now_y),searchLCS(now_x,now_y-1));
    }
    return 0;
}

int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 0; i < n;i++){
        cin >> x;
        cin >> y;
        for(int i = 0; i < x.length()+1;i++){
            for(int l = 0; l < x.length()+1;l++){
                LCS[i][l] = -1;
            }
        }
        cout << searchLCS(x.length()-1,y.length()-1) << endl;
    }
    

    return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

// ---------------------
// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

// ---------------------
#define INF 922337203685477580
typedef long long ll;

int dp[1000][1000];

int main() {
  int q;
  cin >> q;
  REP(loop, q) {
    char S[1000], T[1000];
    cin >> S >> T;

    REP(i, strlen(S)) {
      REP(j, strlen(T)) {
        dp[i][j] = 0;
      }
    }
    for (int i = 0; i < strlen(S); i++) {
      for (int j = 0; j < strlen(T); 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[strlen(S) - 1][strlen(T) - 1] << endl;
  }

  return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int c[maxn][maxn];

int lcs(char s1[], char s2[]){
	int m = strlen(s1);
	int n = strlen(s2);
	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 = 0;i < m;i++){
	
	for(int j = 0;j < n ;j++){
		if(s1[i] == s2[j])
		c[i+1][j+1] = c[i][j] + 1;
		else
		 c[i+1][j+1] = max(c[i][j+1],c[i+1][j]); 
	}
}
 return c[m][n];
}
int main(){
	char s1[maxn],s2[maxn];
	int T;
	cin >> T;
	while(T --){
		cin >> s1 >> s2;
		cout << lcs(s1,s2) << endl; 
		
	} 
	return 0; 
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int MAX_L = 10000;
int q;

string data[MAX_N][2];
ll mem[MAX_L][MAX_L];

ll eval(string &s1, string &s2, int i, int j){
	int ii = i - 1;
	int jj = j - 1;
	if (ii == -1 || jj == -1) return 0;
	if (s1[ii] == s2[jj]) return mem[i - 1][j - 1] + 1;
	if (s1[ii] != s2[jj]) return max(mem[i - 1][j], mem[i][j - 1]);
	throw "exception";
}

ll solve(string s1, string s2){

	int L1 = s1.size();
	int L2 = s2.size();
	rep(i, L1 + 1){
		rep(j, L2 + 1)
		{
			mem[i][j] = eval(s1, s2, i, j);
		}
	}

	return mem[L1][L2];
}

int main() {

	cin >> q;
	rep(i, q){
		cin >> data[i][0];
		cin >> data[i][1];
	}

	rep(i, q){
		cout << solve(data[i][0], data[i][1]) << endl;
	}
}