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++: #ifdef BUILT_LOCAL

#include "niklib.h"

#endif

#include <iostream>
#include <utility>
#include <numeric>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <list>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
constexpr ll mod = 1000000007;

typedef long long num;

#define bs(n) (1ll<<(ll)(n))
#define rep(i, n) for(ll (i) = 0;(i) < (n);(i)++)
#define rrep(i, n) for(ll (i) = 1;(i) <= (n);(i)++)

int v[1010][1010], f[1010][1010][2];

int lcs2(string &a, string &b) {
    memset(v, 0, sizeof(int[1010][1010]));
    memset(f, 0, sizeof(int[1010][1010][2]));
    int n = a.length(), m = b.length(), ri = 0, rj = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j] && v[i + 1][j + 1] < v[i][j] + 1) {
                v[i + 1][j + 1] = v[i][j] + 1;
                f[i + 1][j + 1][0] = i;
                f[i + 1][j + 1][1] = j;
            }
            if (v[i + 1][j] < v[i][j]) {
                v[i + 1][j] = v[i][j];
                f[i + 1][j][0] = i;
                f[i + 1][j][1] = j;
            }
            if (v[i][j + 1] < v[i][j]) {
                v[i][j + 1] = v[i][j];
                f[i][j + 1][0] = i;
                f[i][j + 1][1] = j;
            }
        }
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            if (v[ri][rj] < v[i][j]) {
                ri = i;
                rj = j;
            }
    string ret;
    int rn = v[ri][rj];
    while (ri != 0 && rj != 0) {
        if (f[ri][rj][0] == ri - 1 && f[ri][rj][1] == rj - 1) {
            ret.push_back(a[ri]);
        }
        int rii = f[ri][rj][0];
        int rjj = f[ri][rj][1];
        ri = rii;
        rj = rjj;
    }
    return rn;
}


int main() {
    int q;
    cin >> q;
    string a, b;
    rep(i, q) {
        cin >> a >> b;
        cout << lcs2(a, b) << endl;
    }
}

C++: #include <stdio.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include <cassert>
#include <climits>
#include <vector>
#include <memory>
using namespace std;

#define DEBUG (0)

#if DEBUG
#define DPRINTF(...) do { \
    printf("D(L%d) %s: ", __LINE__, __func__); \
    printf(__VA_ARGS__); \
  } while (false)
#else
#define DPRINTF(...)
#endif // DEBUG


vector<string> makeSubsequences(string str, int length)
{
  if (length == 0)
    return vector<string>();

  DPRINTF("str %s  length %d\n", str.c_str(), length);
  assert(0 <= length && length <= str.length());

  vector<string> subsequences;

  if (length == 1)
  {
    for (int i = 0; i < str.length(); i++)
    {
      subsequences.push_back(str.substr(i, 1));
    }

    return subsequences;
  }

  for (int i = 0; i <= str.length() - length; i++)
  {
    const string substr = str.substr(i + 1, str.length() - (i + 1));
    vector<string> strs = makeSubsequences(substr, length - 1);

    for (string s : strs)
      subsequences.push_back(str[i] + s);
  }

  return subsequences;
}


bool isFindSubseq(string str, string subseq)
{
  DPRINTF("str %s  subseq %s\n", str.c_str(), subseq.c_str());

  assert(str.length() > 0 && subseq.length() > 0);

  int j = 0;

  for (int i = 0; i < str.length(); i++)
  {
    if (str[i] == subseq[j])
      j++;

    if (j == subseq.length())
      return true;
  }

  return false;
}


int setLCSlen(string strShort, string strLong, int idx, int *pLength)
{
  DPRINTF("strLong %s  strShort %s  idx %d\n", strLong.c_str(), strShort.c_str(), idx);

  assert(strShort.length() && strLong.length() && idx >= 0 && pLength);

  if (idx == 0)
  {
    const string s = strShort.substr(0, 1);

    if (isFindSubseq(strLong, s))
      pLength[0] = 1;
    else
      pLength[0] = 0;

    return pLength[0];
  }

  if (!pLength[idx-1])
    setLCSlen(strShort, strLong, idx-1, pLength);

  const string sub = strShort.substr(0, idx);

  vector<string> candidates = makeSubsequences(sub, pLength[idx-1]);

  for (string &s : candidates)
    s = s + strShort[idx];

#if DEBUG
  DPRINTF("Candidates\n");
  for (string s : candidates)
    DPRINTF(" - %s\n", s.c_str());
#endif // DEBUG

  for (string s : candidates)
  {
    if (isFindSubseq(strLong, s))
    {
      pLength[idx] = s.length();
      break;
    }
  }

  if (!pLength[idx])
    pLength[idx] = pLength[idx-1];

  DPRINTF("pLength[%d] %d\n", idx, pLength[idx]);

  return pLength[idx];
}


int getLCSlen(string s0, string s1)
{
  const string* pStrLong;
  const string* pStrShort;

  if (s0.length() < s1.length())
  {
    pStrShort = &s0;
    pStrLong = &s1;
  }
  else
  {
    pStrShort = &s1;
    pStrLong = &s0;
  }

  int *pLongestLens = new int[pStrShort->length()];

  // init
  for (int i = 0; i < pStrShort->length(); i++)
    pLongestLens[i] = 0;

  const int longest = setLCSlen(*pStrShort, *pStrLong, pStrShort->length() - 1, pLongestLens);

  delete [] pLongestLens;

  return longest;
}


int main()
{
  int numOfPair;
  cin >> numOfPair; cin.ignore();

  DPRINTF("num of pair %d\n", numOfPair);

  for (int i = 0; i < numOfPair; i++)
  {
    string str0, str1;
    cin >> str0 >> str1; cin.ignore();

    DPRINTF("str0 %s  str1 %s\n", str0.c_str(), str1.c_str());

    cout << getLCSlen(str0, str1) << endl;
  }

  return 0;
}

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

int C[1001][1001];
string N1, N2;

int lcs()
{
	int m = N1.size();
	int n = N2.size();
	int maxl = 0;

	N1 = " " + N1;
	N2 = " " + N2;

	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 (N1[i] == N2[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()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int q;

	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> N1 >> N2;
		cout << lcs() << endl;
	}
		
	return 0;                                                                            
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <utility>
#include <map>
#include <inttypes.h>

int LCS(std::string s,std::string t){
    int n,m,c[n+1][m+1];
    n=s.size();
    m=t.size();
    int maxlen=0;
    for(int i=0;i<n;i++){
        c[i][0]=0; 
    }
    for(int i=0;i<m;i++){
        c[0][i]=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i]==t[i]){
                c[i][j]=c[i-1][j-1]+1;
            }else{
                c[i][j]=std::max(c[i-1][j],c[i][j-1]);
            }
            maxlen=std::max(c[i][j],maxlen);
        }
    }
    return maxlen;
}
int main(){
	int N;
    
    std::cin >> N;
    std::string s1,s2;
    for(int i=0;i<N;i++){
        std::cin >> s1 >> s2;
        std::cout << LCS(s1,s2) <<std::endl;
    }
        
    
    return 0;
}