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 <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <utility>
#include <map>
#include <inttypes.h>
int c[1001][1001] = {0};
/*int LCS(std::string s, std::string t){
    int n, m, c[1001][1001] = {0};
    n = s.size();
    m = t.size();
    int maxlen = 0;
    for(int i = 1; i <= n; i++){
        c[i][0] = 0;
    }
    for(int i = 1; i <= m; i++){
        c[0][i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s[i - 1] == t[j - 1]){
                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(maxlen, c[i][j]);
        }
    }
    return maxlen;
}*/
int main(){
    int N;

    std::cin >> N;
    std::string s1, s2;
    for(int i = 0; i<N; i++){
        std::cin >> s1 >> s2;
        int n, m;
        n = s1.size();
        m = s2.size();
        int maxlen = 0;
        for(int i = 1; i <= n; i++){
            c[i][0] = 0;
        }
        for(int i = 1; i <= m; i++){
            c[0][i] = 0;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s1[i - 1] == s2[j - 1]){
                    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(maxlen, c[i][j]);
            }
        }
        std::cout << maxlen << std::endl;
    }
    return 0;
}

C++: #include <stdio.h>
#include <string.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repi(i, n) for(int i = 1; i < n; ++i)

int max(int a, int b) {
  return a > b ? a : b;
}

int main(void) {
  int n;
  scanf("%d", &n);
  rep(i, n) {
    char x[1500], y[1500];
    int h, w;
    scanf("%s", x);
    scanf("%s", y);
    h = strlen(x), w = strlen(y);
    int dp[h][w], len[w], maxs = 0;
    rep(j, h) rep(k, w) dp[j][k] = 0;
    rep(j, w) if(x[0] == y[j]) dp[0][j] = 1, maxs = 1;
    len[0] = 0;
    repi(j, w) len[j] = max(dp[0][j - 1], len[j - 1]);
    repi(j, h) {
      rep(k, w) if(x[j] == y[k]) {
        dp[j][k] = len[k] + 1;
        if(maxs < dp[j][k]) maxs = dp[j][k];
      }
      repi(k, w) len[k] = max(dp[j][k - 1], max(len[k], len[k - 1]));
      /*rep(k, w) printf("%d ", len[k]);
      printf("\n");*/
    }
    /*printf("\n");
    rep(j, h) {
      rep(k, w) printf("%d ", dp[j][k]);
      printf("\n");
    }*/
    printf("%d\n", maxs);
  }
  return 0;
}

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

int lcs(string &X, string &Y) {
  int dp[1000 + 1][1000 + 1];
  int max = 0;
  int m = X.size();
  int n = Y.size();
  X = ' ' + X;
  Y = ' ' + Y;

  for (int i = 1; i <= m; i++)
    dp[i][0] = 0;

  for (int i = 1; i <= n; i++)
    dp[0][i] = 0;

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i] == Y[j])
	dp[i][j] = dp[i-1][j - 1] + 1;
      else if (dp[i - 1][j] >= dp[i][j - 1])
	dp[i][j] = dp[i - 1][j];
      else
	dp[i][j] = dp[i][j - 1];

      if(max < dp[i][j])
	max = dp[i][j];
    }
  }

  return max;
}

int main() {
  int N = 0;
  cin >> N;

  string X, Y;
  for (int i = 0; i < N; i++) {
    cin >> X >> Y;

    cout << (int)lcs(X, Y) << endl;
  }

  return 0;
}

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

void solve(string X, string Y);

int main(int argc, char const *argv[]) {
	int N;
	cin >> N;


	for (int i = 0; i < N; i++) {
		string X, Y;
		cin >> X >> Y;
		solve(X, Y);
	}

	return 0;
}

void solve(string X, string Y) {
	int **c = new int*[1000 + 1];
	for (int i = 0; i < 1000 + 1; i++)
		c[i] = new int[1000 + 1];

	int max = 0;
	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 i = 1; i <= n; i++)
	  c[0][i] = 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 if (c[i - 1][j] >= c[i][j - 1])
	      c[i][j] = c[i - 1][j];
	    else
	      c[i][j] = c[i][j - 1];

	    max = (max < c[i][j]) ? c[i][j] : max;
	  }
	}

	cout << max << endl;

	for (int i = 0; i < 1000 + 1; i++)
		delete c[i];

	delete[] c;
}

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

static const int N = 1000;

int longestCommonSubsequence(string X, stringY)  {
  int c[N + 1][N + 1];
  int m = X.size();
  int n = Y.size();
  intmax1 = 0;
  X = ' ' + X;
  Y = ' ' + Y;
  for (int i = 0; i <= m; i++) 
    c[i][0] = 0;
  for (int j = 1; j <= n; j++)
    s[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]);
      }
      max1 = max(max1, c[i][j]);
    }
  }
  return max1;
}
 
int main()  {
  string s1, s2;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)  {
    cin >> s1 >> s2;
  cout << longestCommonSubsequence(s1, s2) << endl;
  }
  return ;
}

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; // X[0]に空白を挿入
    Y = ' ' + Y;
    for (int i=0; i<m; i++) C[i][0] = 0;
    for (int j=0; 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][j-1], C[i-1][j]);
            }
            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;
}

C++: #include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<string, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int q;
    cin >> q;
    while (q--)
    {
        string s, t;
        cin >> s >> t;
        int n = s.length(), m = t.length();
        s = "$" + s;
        t = "$" + t;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s[i] == t[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        cout << dp[n][m] << endl;
    }
}