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<algorithm>
using namespace std;

int main(){
  
  int q, lcs[1010][1010] = {};
  string a, b;

  //input
  cin >> q;
  for(int i = 0;i < q;i++){
    cin >> a;
    cin >> b;

    for(int r = 0;r < (int)a.size();r++){
      for(int c = 0;c < (int)b.size();c++){
	//if a_i = b_j, chain a_i to LCS of a_{i-1} and b_{j-1}
        if(a[r] == b[c]) lcs[r + 1][c + 1] = lcs[r][c] + 1;
	//else LCS of a_{i-1} and b_j or a_i and b_{j-1}
        else lcs[r + 1][c + 1] = max(lcs[r + 1][c], lcs[r][c + 1]);
      }
    }
    
    //output
    cout << lcs[a.size()][b.size()] << endl;
  }
  
  return 0;
}

C++: // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

#define debug(x) cout << #x << "==" << x << endl;

using namespace std;

//??\???
#define MAX_LEN 1000
int N;
int dp[MAX_LEN + 1][MAX_LEN + 1];

void print_dp_table(int n, int m) {
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cout <<setw(2) << dp[i][j];
    }
    cout << "\n";
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);

  cin >> N;

  string s1, s2;

  while( cin >> s1 >> s2 ) {

    std::vector<char> a;
    std::vector<char> b;
    for(char& c : s1) {
      a.push_back(c);
    }
    for(char& c : s2) {
      b.push_back(c);
    }


    // dp ????????????????????????
    fill(dp[0], dp[MAX_LEN + 1], 0);

    for( int i = 0; i < (int)a.size(); i++) {
      for( int j = 0; j < (int)b.size(); j++) {
        if( a[i] == b[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]);
        }
      }
    }

    // print_dp_table(a.size(), b.size());
    cout << dp[a.size()][b.size()] << endl;

  }

  return 0;
}

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

int dp[1005][1005];
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int lcs(string &x, string &y) {
    memset(dp, 0, sizeof(dp));
    int xn = x.size();
    int yn = y.size();
    rep(i, xn) {
        rep(j, yn) {
            if (x[i] == y[j])
                dp[i + 1][j + 1] = max(dp[i][j] + 1, max(dp[i][j + 1], dp[i + 1][j]));
            else
                dp[i + 1][j + 1] = max(dp[i][j], max(dp[i][j + 1], dp[i + 1][j]));
        }
    }
    return dp[xn][yn];
}

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        string x, y;
        cin >> x >> y;
        int ans = lcs(x, y);
        cout << ans << endl;
    }
}

C++: #include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
const ll INF=1e9+7;
const ll N = 1007;


ll LCS(string x,string y){
	ll xs,ys;
	xs=x.size();ys=y.size();
	ll dp[xs+1][ys+1];
	FOR(i,0,xs+1)FOR(j,0,ys+1)dp[i][j]=0;
	FOR(i,0,xs+1){
		FOR(j,0,ys+1){
			if(i==0||j==0)dp[i][j]=0;
			else{
				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]);
			}
		}
	}
	return dp[xs][ys];
}



int main(){
	ll n;
	cin>>n;
	FOR(i,0,n){
		string x,y;
		cin>>x>>y;
		cout<<LCS(x,y)<<endl;
	}
}

C++: #include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
int main(){
	int n;
	cin >> n;
	while(n--){
		string a,b;
		cin >> a >> b;
		int asize = a.size(),bsize = b.size();
		vector<vector<int> > dp(asize+1,vector<int>(bsize+1,0));
		for(int i=1;i<asize+1;i++){
			bool is_match = false;
			for(int j=1;j<bsize+1;j++){
				if(!is_match){
					if(a[i-1] == b[j-1]){
						dp[i][j] = dp[i-1][j] + 1;
						is_match = true;
					}else{
						dp[i][j] = dp[i-1][j];
					}
				}else{
					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
		/*		for(int i = 0;i<asize+1;i++){
		copy(dp[i].cbegin(),dp[i].cend(),ostream_iterator<int>(cout, " ") );
		cout << endl;
		}*/
				
		cout << dp[asize][bsize] << endl;
	}
}

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

int LCS(int len[],char S[][1001]){//???????????????2?????§?????????
    int DP[1001][1001] = {};
    for (int i = 1; i <= len[0]; i++) {
        for (int j = 1; j <= len[1]; j++) {
            if(S[0][i-1] == S[1][j-1]){
                DP[i][j] = DP[i-1][j-1]+1;
            }else{
                DP[i][j] = max(DP[i-1][j],DP[i][j-1]);
            }
        }
    }
    
    return DP[len[0]][len[1]];
}

void solve(){
    char S[2][10001];
    scanf("%s %s",S[1],S[2]);
    len[0] = strlen(S[0]);
    len[1] = strlen(S[1]);
    int len[2];
    int ll;
    ll = LCS(len,S);
    printf("%d\n",ll);
}

int main(){
    int N;
    cin >> N;
    for (int i = 0; i < n; i++) {
        solve();
    }
    
    return 0;
}

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

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

int	dp[1001][1001] = {};

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

	int maxl;
	string s1, s2;
	REP( i, n ) {
		cin >> s1 >> s2;
		maxl = 0;
		REP( j, s1.size() ) {
			REP( k, s2.size() ) {
				if( s1[j] == s2[k] ) {
					dp[j][k] = dp[j - 1][k - 1] + 1;
				} else {
					dp[j][k] = max( dp[j - 1][k], dp[j][k - 1] );
				}
				maxl = max( dp[j][k], maxl );
			}
		}

		cout << maxl << endl;
	}
}

C++: 27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include<iostream>
#include<vector>
#include<limits.h>
#include<string>
using namespace std;
 
int LCS(string a, string b){
    int m=a.size();
    int n=b.size();
    int T[m+1][n+1];
    int i,j;
    for (i=0;i<m+1;i++) T[i][0]=i;
    for (j=0;j<n+1;j++) T[0][j]=j;
    for (i=1;i<m+1;i++){
        for (j=1;j<n+1;j++){
            int min=T[i-1][j]+1;
            if (min>T[i][j-1]+1){
                min=T[i][j-1]+1;
            }
            if ((a[i-1]==b[j-1])&&(min>T[i-1][j-1]+1)){
                min=T[i-1][j-1]+1;
            }
            T[i][j]=min;
        }
    }
    return m+n-T[m][n];
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m,i;
    cin >> m;
     
    string a,b;
    for (i=0;i<m;i++){
        cin >> a >> b;
        cout << LCS(a,b) << endl;
    }
    return 0;
}