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 <string>
using namespace std;
static const int MAX = 1001;

void lcs(string X, string Y) {
	int dp[MAX][MAX];  
	int i,j;

	int xLength = X.size();
	int yLength = Y.size();


	// initialize dp[][]
	for (i = 1; i <= xLength; i++)
		dp[i][0] = 0;
	for (i = 1; i <= yLength; i++)
		dp[0][i] = 0;

	for (i = 1; i <= xLength; i++){
		for (j = 1; j <= yLength; j++){
			// Because the original string is 0-based , so subtracted from 1
			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]);
			}
		}
	}

	// testing code: print out the dp[][]
	cout << "j";
	for (j = 1; j <= yLength; j++)
		cout << ' ' << j ;
	cout << endl;
		

	for (i = 1; i <= xLength; i++){
		cout << i << '.';
		for (j = 1; j <= yLength; j++){
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}

	cout << dp[xLength][yLength] << endl;
}

int main() {
	int n , i;
	string X, Y;

	cin >> n;
	for (i = 0 ; i < n; i++ ) {
		cin >> X;
		cin >> Y;
		lcs(X, Y);
	}

	return 0;

}

C++: 
#include<bits/stdc++.h>
using namespace std;
#define mx 1007
string a,b;
int dp[mx][mx];
bool visited[mx][mx];

void init(int n)
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        visited[i][j]=false;
    }
}

int lcs(int i,int j)
{
    if(i==a.size() || j==b.size())
    {
        return 0;
    }

    if(visited[i][j])return dp[i][j];

    int ans=0;
    if(a[i]==b[j])
        ans=1+lcs(i+1,j+1);
    else ans+=max(lcs(i+1,j),lcs(i,j+1));

    dp[i][j]=ans;
    visited[i][j]=true;
    return dp[i][j];
}

int main()
{


 int n;
 cin>>n;
 while(n--)
 {
     cin>>a>>b;
     init(max(a.size(),b.size()));
     cout<<lcs(0,0)<<endl;
 }






    return 0;
}

C++: #include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
//#include<utility>
//#include<initializer_list>
//#include<tuple>
//#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
bool isSubstring(string substr, string t) {
	int n = substr.length();
	int seek = 0;
	rep(i, n) {
		bool ex = 0;
		for (int j = seek; j < t.length(); j++) {
			if (substr[i] == t[j]) {
				ex = 1;
				seek = j + 1;
				break;
			}
		}
		if (ex) {
			continue;
		}
		else {
			return false;
		}
	}
	return true;

}

int LongestCommonSubstring(string s, string t) {
	vector<int>dp(s.length(), 0);
	int n = s.length();
	string lcs = "";
	if (isSubstring(s.substr(n - 1, n), t)) {

		dp[n - 1] = 1;
		lcs = s[n - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		//string substr = s.substr(i, n);
		string substr = s[i] + lcs;
		int issubst = isSubstring(substr, t);
		if (issubst) lcs = substr;
		dp[i] = dp[i + 1] + issubst;
	}
	return dp[0];
}
int main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring("bacd", "becd") << endl;
	//cout << LongestCommonSubstring("abcd", "becd") << endl;
	int q;
	cin >> q;
	vector<string> s(q);
	vector<string> t(q);
	rep(i, q) {
		cin >> s[i] >> t[i];
	}
	rep(i, q) {
		cout << LongestCommonSubstring(s[i], t[i]) << endl;
	}

	return 0;
}

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

string X, Y;
int v[1001][1001];

int  dp(string X, string Y) {
	int n = X.size();
	int m = Y.size();
	memset(v, 0, sizeof(v));
	for (int i = 0; i <= n; i++) {
		v[i][0] = 0;											///０のテーブル
		for (int j = 0; j <= m; j++) {
			v[0][j] = 0;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (X[i-1] == Y[j-1]) {
				v[i][j] = v[i - 1][j - 1] + 1;
			}
			else {
				v[i][j] = max(v[i - 1][j], v[i][j - 1]);
			}
		}
	}
	return v[n][m];
}

int main(void)
{
	int x;
	cin >> x;
	
	for (int i = 0; i < x; i++) {
		cin >> X >> Y;
		int ans = dp(X, Y);
		cout << ans << endl;
	}
	
	
}

C++: # include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
constexpr int MOD = 1000000007;
constexpr int INF = 2000000000;
using namespace std;

int lcs(string x, string y) {
	int c[10][10];
	int m = x.size();
	int n = y.size();
	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;
	c[0][0] = 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]);
			}
		}
	}
	return c[m][n];
}

int main() {
	int n;
	cin >> n;
	string a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		cout << lcs(a, b) << endl;
	}
}

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

int main(){
  int n;
  char x[1001],y[1001];
  int dp[1002][1002];
  


  //load n;
  cin >>n;
  for(int i=0;i<n;i++){
    //initialize
    for(int i=0;i<1002;i++){
      for(int j=0;j<1002;j++){
	dp[i][j]=0; 
      }
    }
    //load string
    scanf("%s",x);
    scanf("%s",y);
    //dp
    for(int j=0;j<strlen(x);j++){
      for(int k=0;k<strlen(y);k++){
	if(x[j]==y[k]){
	  dp[j+1][k+1]=dp[j][k]+1;
	}

	else{
 
	  if(dp[j][k+1]>dp[j+1][k]){
	    dp[j+1][k+1]=dp[j][k+1];
	  }

	  else{
	    dp[j+1][k+1]=dp[j+1][k];
	  }
	}
      }
    }

    //print
    cout <<dp[strlen(x)][strlen(y)]<<endl;
  }



  return 0;
}

C++: #include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAX 1001
void solve(void);
int q,count[MAX][MAX]={},xlength,ylength;
char X[MAX],Y[MAX];
 
void solve(void){
  int i,j;
 
  xlength=strlen(X);
  ylength=strlen(Y);
   
  for(i=1;i<=xlength;i++){
    for(j=1;j<=ylength;j++){
      if(X[i-1]==Y[j-1]) count[i][j]=count[i-1][j-1]+1;
      else if(count[i-1][j]>=count[i][j-1]) count[i][j]=count[i-1][j];
      else count[i][j]=count[i][j-1];
    }
  }
}
     
int main()
{
  int i;
   
  scanf("%d",&q);
 
  for(i=1;i<=q;i++){
    scanf("%s",X);
    scanf("%s",Y);
    solve();
    printf("%d\n",count[xlength][ylength]);
  }
 
  /*for(i=0;i<q;i++){
    printf("%d\n",count[][]);
    }*/
 
  return 0;
}