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 <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
// const int INF = +100100100;
// typedef pair<int,int> P;

// int dp(int i, int j, string x, string y, char D[MAX][MAX]){
//     if(x[i-1]==y[j-1])return D[i-1][j-1]+1;
//     else{
//         return max(D[i-1][j],D[i][j-1]);
//     }
// }

int lcs(string x, string y){
    int D[x.size()+1][y.size()+1];
    rep(i,x.size()+1)D[i][0]=0;
    rep(i,y.size()+1)D[0][i]=0;
    rrep(i,x.length()){
        rrep(j,y.length()){
            if(x[i-1]==y[j-1])D[i][j]= D[i-1][j-1]+1;
            else{
                D[i][j]= max(D[i-1][j],D[i][j-1]);
            }
        }
    }
    int ans = D[x.length()][y.length()];
    return ans;
}

int main(){
    int n;cin>>n;
    rep(i,n){
        string x,y;
        cin >> x >> y;
        printf("%d\n",lcs(x,y));
    }
    return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map <char,vector<int>> alx,aly;//x,y
int memo[1010][1010];
string x,y,q;
int lcs(int xn,int yn){//yn文字目以降でX[xn]と同じやつを探す
    if(memo[xn][yn]!=-1)return memo[xn][yn];
    int ans=0;
	/*
    for(int i=xn; i<x.size();i++){
        for(int j=yn; j<y.size(); j++){
            if(alx[x[i]]==aly[y[j]]){
                ans=max(ans,lcs(i+1,j+1)+1);
            }
        }
    }
	*/
	for(int i=xn; i<x.size();i++){
        for(int j=0; j<aly[x[i]].size(); j++){
			if(aly[x[i]][j] < yn) continue;
			ans=max(ans,lcs(i+1,aly[x[i]][j]+1)+1);
		}
    }
    return memo[xn][yn]=ans;
}
 
 
int main(){
    int q;
    cin >> q;
    for(int ds=0; ds<q; ds++){
 
        cin >> x >> y;
        for(int i=0; i<=x.size(); i++){
            for(int j=0; j<=y.size(); j++){
				memo[i][j]=-1;
			}
        }

		for(int i=0; i<x.size(); i++) alx[x[i]].push_back(i);
		for(int i=0; i<y.size(); i++) aly[y[i]].push_back(i);
		

        //memset(memo, -1, sizeof(memo));
         
        cout << lcs(0,0) << 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];

void solve()
{
  REP(i, str1.size())
    if(str1[i] == str2[str2.size() - 1])
      dp[i][str2.size() - 1] = 1;
    else
      dp[i][str2.size() - 1] = 0;
  for(int i = str2.size() - 2; i >= 0; i--)
    if(str1[str1.size() - 1] == str2[i])
      dp[str1.size() - 1][i] = 1;
    else
      dp[str1.size() - 1][i] = dp[str1.size() - 1][i + 1];
  for(int i = str1.size() - 2; i >= 0; i--){
    for(int j = str2.size() - 2; j >= 0; j--){
      if(str1[i] == str2[j])
	dp[i][j] = dp[i + 1][j + 1] + 1;
      else
	dp[i][j] = max(dp[i + 1][j], dp[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);
    solve();
    cout << dp[0][0] << endl;
  }
}

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

#define MAX_N 1000
#define MAX_M 1000

void solve();

string s, t;
int dp[MAX_N + 1][MAX_M + 1];

void solve(){
	for(int i = 0; i < s.length(); i++){
		for(int j = 0; j < t.length(); j++){
			if(s[i] == t[j]){
				dp[i + 1][j + 1];
					dp[i + 1][j + 1] = dp[i][j] + 1;
				} else {
					dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][j]);
				}
			}
		}
		cout << dp[s.length()][t.length()] << endl;
}

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> s >> t;
		solve();
	}
	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 q;
  cin >> q;

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

  return 0;
}

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

using namespace std;

int lcs(char x[],char y[]);

int main(){
	char x[1000],y[1000];
	int n,*memo; cin>>n;
	memo = new int[n];
	for(int i=0;i<n;i++){
		cin>>x>>y;
		memo[i] = lcs(x,y);
	}
	for(int i=0;i<n;i++)
		cout<<memo[i]<<endl;

	delete [] memo;
}

int lcs(char x[],char y[]){
	int m = strlen(x), n = strlen(y);
	int **c,a;
	c = new int*[m+1]; for(int i=0;i<=m;i++) c[i] = new int[n+1];
	for(int i=0;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-1]==y[j-1]){
				c[i][j] = c[i-1][j-1]+1;
				if(i==m&&j==n){
					a = c[i][j];
					//cout<<c[i][j]<<endl;
				}
			}else{
				if(c[i-1][j]>=c[i][j-1]){
					c[i][j] = c[i-1][j];
					if(i==m&&j==n){
						a = c[i][j];
						//cout<<c[i][j]<<endl;
					}
				}else{
					c[i][j] = c[i][j-1];
					if(i==m&&j==n){
						a = c[i][j];
						//cout<<c[i][j]<<endl;
					}
				}
			}
		}
	}
	for(int i=0;i<=strlen(x);i++) delete [] c[i]; delete [] c;
	return a;
}

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

int lcs(string X,string Y){
  int c[1001][1001];
  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=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(){
  int q;cin>>q;
  while(q--){
    string a,b;cin>>a>>b;
    cout<<lcs(a,b)<<endl;
  }
  return 0;
}

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

using namespace std;

int q;
string A, B;

void findlongest() {
	int res[1001][1001];
	A = ' '+A ;
	B = ' '+B ;
	int l1 = A.size();
	int l2 = B.size();
	int max = 0;
	int j;
	for (int i = 0; i < l1; ++i) {
		for (j = 0; j < l2; ++j) {
			if (i == 0) {
				res[0][j] = 0;
			}
			else if (j == 0) {
				res[i][0] = 0;
			}
			else {
				if (A[i] == B[j]) {
					res[i][j] = res[i - 1][j - 1] + 1;
					if (max < res[i][j]) {
						max = res[i][j];
					}
				}
				else {
					if (res[i - 1][j] >= res[i][j - 1]) {
						res[i][j] = res[i - 1][j];
					}
					else {
						res[i][j] = res[i][j - 1];
					}
				}
			}
			//cout << res[i][j] << ' ';
		}
		//cout << endl;
	}

	cout << max << endl;
}

int main() {
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> A;
		cin >> B;
		findlongest();
	}
	return 0;
}