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>
int main()
{
  int n;
  int an[1000];
  int l=0;
  std::cin>>n;
  std::string x;
  std::string y;
  int ans[1000][1000];
  int j,k;
  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<1000;j++){
      for(int k=0;k<1000;k++){
	ans[j][k]=0;
      }
    }
    for(int j=0;j<x.size();j++){
      for(int k=0;k<y.size();k++){
	if(x[j]==y[k]){
	  ans[j][k]=ans[j-1][k-1]+1;
	}else{
	  if(ans[j][k-1]>ans[j-1][k]){
	    ans[j][k]=ans[j][k-1];
	  }else{
	    ans[j][k]=ans[j-1][k];
	  }
	}
      }
    }
    std::cout<<ans[x.size()-1][y.size()-1]<<'\n';  
  }
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int solve(char* x,char* y){
    int n=strlen(x),m=strlen(y);
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    for(int i=0;i<n+1;i++){
        if(!i)continue;
        for(int j=0;j<m+1;j++){
            if(!j)continue;
            if(x[i-1]==y[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    return dp[n][m];
}
int main(){
    int q;scanf("%d",&q);
    while(q--){
        char x[1000],y[1000];
        scanf("%s%s",x,y);
        printf("%d\n",solve(x,y));
    }
    return 0;
}

C++: #include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=1e9;
int dp[1001][1001];
int main(){
      string s,t;
      int n;
      cin>>n;
      while(n--){
            cin>>s>>t;
            memset(dp,0,sizeof(dp));
            REP(i,s.size()){
                  REP(j,t.size()){
                        if(s[i]==t[j])dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
                        else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                  }
            }
            cout<<dp[s.size()][t.size()]<<endl;
      }
}

C++: #include <bits/stdc++.h>
#include<algorithm>
#define int long long
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1000000000000
int MOD=1000000007;
int n;
int dp[1001][1001];
signed main() {
cin>>n;
rep(ii,n){
  rep(p,1001){
    rep(q,1001){
      dp[p][q]=0;
    }
  }
  string x,y;
  cin>>x>>y;
  rep(i,x.size()){
    rep(j,y.size()){
      if(x[i]==y[j]){dp[i+1][j+1]=1+dp[i][j];}
      else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
    }
  }
cout<<dp[x.size()][y.size()]<<endl;
 }
}

C++: #include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;

ll N;

void lcs(string a, string b){
    int DP[a.size()+1][b.size()+1]={{0}};
    for(int i=0;i<=a.size();i++) DP[i][0]=0;
    for(int i=0;i<=b.size();i++) DP[0][i]=0;
    for(int i=1;i<=a.size();i++){
        for(int j=1;j<=b.size();j++){
            if(a[i-1]==b[j-1]) DP[i][j] = DP[i-1][j-1] + 1;
            else DP[i][j] = max(DP[i][j-1], DP[i-1][j]);
            //cout << " " << DP[i][j];
        }
        //cout << endl;
    }
    cout << DP[a.size()][b.size()] << endl;
    return;
}

signed main(){
    cin >> N;
    for(int i=0;i<N;i++){
        string A, B;
        cin >> A >> B;
        lcs(A, B);
    }
    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 1;
    }
  }
  if(str1[i] == str2[j]){
    k = j + 1;
    dp[i][j] = solve(i + 1, j + 1);
    return dp[i][j] + 1;
  }else{
    return solve(i, j + 1);
  }
}

int main()
{
  int q, n, ans = 0;
  cin >> q;
  cin.ignore();
  fill(&dp[0][0], &dp[1001][0], -1);
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    REP(i, str1.size()){
      n = solve(i, 0) - 1;
      ans = (n > ans) ? n : ans;
    }
  }
  cout << ans << endl;
}

C++: #include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int q;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> q;
    while (q-->0) {
        string x, y; cin >> x >> y;
        vvll dp(x.size() + 1, vll(y.size() + 1, 0));
        for (int xi = 0; xi < x.size(); xi++) {
            for (int yi = 0; yi < y.size(); yi++) {
                if (x[xi] == y[yi]) dp[xi + 1][yi + 1] = dp[xi][yi] + 1;
                else dp[xi + 1][yi + 1] = max(dp[xi][yi + 1], dp[xi + 1][yi]);
            }
        }
        cout << dp[x.size()][y.size()] << '\n';
    }
    return 0;
}