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;
string x,y;
int dp[1005][1005];
int lcs(string x,string y)
{

    int Max=-1;
    int n=x.size(),m=y.size();
    x=' '+x;
    y=' '+y;
    for(int i=1;i<=n;i++)dp[i][0]=0;        //边界条件就是从此开始的，所以要置为1，
    for(int i=1;i<=m;i++)dp[0][i]=0;        //不然循环查询的次数多了就会造成错误
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
         if(x[i]==y[j])dp[i][j]=dp[i-1][j-1]+1;
         else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
         //Max=max(Max,dp[i][j]);
        }
    return dp[n][m];
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
         cin>>x>>y;
        cout<<lcs(x,y)<<endl;
    }
    return 0;
}

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

signed main(void){
  
  int q; cin >> q;
  while(q--){
    string s,t; cin >> s >> t;
    int n = s.size(); int m = t.size();
    
    vector<vector<int>> dp(n+10,vector<int>(m+10,0));
    vector<vector<int>> M(n+10,vector<int>(m+10,0));
    
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){ 
        
        if(s[i] == t[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+1][j],dp[i][j+1]);
        }
        
      }
    }
    
    cout << dp[n][m] << endl;
    
  }
  
  return 0;
}

C++: /*
** Longest Common Subsequence
*/

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;

const int MAX = 1000 + 5;

char s1[MAX], s2[MAX];
int c[MAX][MAX];

int lcs() {
    int m = strlen(s1+1);
    int n = strlen(s2+1);
    c[0][0] = 0;
    int maxl = 0;
    for (int i = 1; i <= m; i++) {
        c[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
        c[0][i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i] == s2[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            }
            else {
                c[i][j] = max(c[i][j - 1], c[i - 1][j]);
            }
            maxl = max(maxl, c[i][j]);
        }
    }

    return maxl;
}

void solve() {
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%s %s", s1+1, s2+1);
        printf("%d\n", lcs());
    }
}

int main() {
    // freopen("infile", "r", stdin);
    // freopen("outfile", "w", stdout);
    solve();
    return 0;
}

C++: #include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int lcs(string,string);

int main(){
  int i,n;
  string st1,st2;

  cin >> n;
  for(i = 0; i < n; i++){
    cin >> st1 >> st2;
    cout << lcs(st1,st2) << endl;
  }
  return 0;
}

int lcs(string st1,string st2){
  int preMax = 0;
  int m,n,i,j;
  int key[MAX+1][MAX+1];

  m = st1.size();
  n = st2.size();
  /**/
  st1 = ' '+st1;
  st2 = ' '+st2;
  for(i = 1; i <= m; i++){
    key[i][0] = 0;
  }
  for(j = 1; j <= n; j++){
    key[0][j] = 0;
  }
  for(i = 1; i <= m; i++){
    for(j = 1; j <= n; j++){
      if(st1[i] == st2[j]){
        key[i][j] = key[i-1][j-1]+1;
      }
      else{
        key[i][j] = max(key[i-1][j],key[i][j-1]);
      }
      preMax = max(preMax,key[i][j]);
    }
  }
  return preMax;
}

C++: #include <iostream>
#include <algorithm>
using namespace std;
int LCS(char *x,char *y);
char x[1000], y[1000];
int lcs[1000][1000];
int main()
{
	int q,i,j;

	cin >> q;
	for (i = 0; i < q; i++) {
		cin >> x;
		cin >> y;
		cout << LCS(x, y) << endl;
	}
}

int LCS(char *x, char *y)
{
	int i, j;
	int len_x, len_y;
	len_x = strlen(x);
	len_y = strlen(y);
	
	for (i = 0; i < len_x; i++) {
		if (x[0] == y[i]) {
			lcs[0][i] = 1;
		}
		else {
			lcs[0][i] = 0;
		}
	}
	for (i = 0; i < len_x; i++) {
		if (x[i] == y[0]) {
			lcs[i][0] = 1;
		}
		else {
			lcs[i][0] = 0;
		}
	}

	for (i = 0; i < len_x; i++) {
		for (j = 0; j < len_y; j++) {
			if (x[i] == y[j]) {
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
				//printf("lcs[%d][%d]=%d\n", i, j, lcs[i - 1][j - 1] + 1);
			}
			if (x[i] != y[j]) {
				lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
				//printf("lcs[%d][%d]=%d\n", i, j, max(lcs[i - 1][j], lcs[i][j - 1]));
			}
		}
	}
	//cout << endl;

	for (i = 0; i < len_x; i++) {
		for (j = 0; j < len_y; j++) {
			//printf("%d ", lcs[i][j]);
		}
		//cout << endl;
	}
	//cout << "len_x=" << len_x << endl << "len_y=" << len_y << endl;
			
	return lcs[len_x-1][len_y-1];
}

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 n; 

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

  return 0;
}