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 <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#include <cassert>
#define rep(i, n) for (int i = 0; i < n; i++)
#define PI 3.14159265358979323846
#define MOD 1000000007
#define vi vector<int>
using namespace std;
using ll = long long;

// ----ここから下は以前競プロをやっていた時に使っていたものです----　

const int MAX = 1000000;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

template <class T> struct cord{
  T x,y;
};

template <class T> double dist(cord<T> a, cord<T> b){
  T dx=a.x-b.x;
  T dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

struct s{
  int p,i,r;
};

//比較関数（降順）
bool cmpP(const s &a, const s &b){
  return a.p > b.p;
}

//比較関数（昇順）
bool cmpI(const s &a, const s &b){
  return a.i < b.i;
}

// ----本問について----
// 問題：最長共通部分列
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C
// 所要時間：30分
// 学んだこと：自分のやってることがDPなのかメモ化再帰（？）なのかよくわからない
// ------------------

// ----ここから本問のソースコード----

// グローバル変数（入力）
ll q, L[1010][1010];
string X,Y;

ll solve(ll i, ll j) {
  if (L[i][j] != -1){return L[i][j];}

  if (i == 0 || j == 0){L[i][j]=0;}
  else if (X[i-1]==Y[j-1]){L[i][j]=solve(i-1,j-1)+1;}
  else {L[i][j]=max(solve(i-1, j), solve(i, j-1));}

  return L[i][j];
}

int main()
{
  //cout << fixed << setprecision(10);
  cin >> q;
  rep(ii,q){
    cin >> X;
    cin >> Y;
    ll x=X.size();
    ll y=Y.size();
    rep(i, 1010){
      rep(j, 1010){
        L[i][j]=-1;
      }
    }
    cout << solve(x, y) << endl;
  }

  return 0;
}

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

int LCS(string a, string b)
{
    int ret;
    int i, j;
    int len1, len2;
    int result[1001][1001] = {0};

    len1 = a.length();
    len2 = b.length();

    for (i = 1; i < len1; i++) {
        for (j = 1; j < len2; j++) {
            if (a[i] == b[j]) {
                result[i][j] = result[i - 1][j - 1] + 1;
            }
            else {
                result[i][j] = max(result[i][j - 1], result[i - 1][j]);
            }
        }
    }

    return result[len1 - 1][len2 - 1];
}

int main(void)
{
    int i;
    int num;
    int ret;
    string a, b;

    scanf("%d", &num);
    for (i = 0; i < num; i++) {
        cin >> a;
        cin >> b;
        ret = LCS(a, b);
        printf("%d\n", ret);
    }

    return 0;
}

C++: #include<iostream>
#include<string.h>
#include<algorithm>

#define MAX 1000

using namespace std;

int lcs(string s1, string s2) {
    int C[MAX+1][MAX+1];
    int m = s1.size();
    int n = s2.size();
    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 (s1[i-1] == s2[j-1]) {
                C[i][j] = C[i-1][j-1] + 1;
            }
            else {
                C[i][j] = max(C[i][j-1], C[i-1][j]);
            }
        }
    }

    return C[m][n];
}

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

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int LCS(char s[],char t[])
{
    int c[50][50];
    int i,j;
    int n = strlen(s);
    int m = strlen(t);
    int maxx = 0;
    for(i=0;i<n;i++)
        c[i][0] = 0;
    for(j=0;j<m;j++)
        c[0][j] = 0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(s[i] == t[j])
                c[i][j] = c[i-1][j-1]+1;
            else
                c[i][j] = max(c[i-1][j],c[i][j-1]);
            maxx = max(maxx,c[i][j]);
        }
    }
    return maxx;
}
int main()
{
    char s[50],t[50];
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",s);
        scanf("%s",t);
        int p = LCS(s,t);
        printf("%d\n",p);
    }

    return 0;
}

C++: 
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+5;

int dp[maxn][maxn];
string s1,s2;

void lcs()
{
    int len1=s1.size();
    int len2=s2.size();
    s1=" "+s1;
    s2=" "+s2;
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(s1[i]==s2[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
//    for(int i=0;i<=len1;i++){
//        for(int j=0;j<=len2;j++){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    cout<<dp[len1][len2]<<endl;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s1>>s2;
        lcs();
    }
    return 0;
}

C++: #define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
using namespace std;
const int num = 1001;
int lg[num + 1][num + 1];
int main() {
	int n, m;
	char s[num], t[num];
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> s[i];
	for (int i = 0; i < m; i++) cin >> t[i];
	for (int i = 0; i < n; i++) lg[i][0] = 0;
	for (int i = 0; i < m; i++) lg[0][i] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (s[i] == t[j]) lg[i + 1][j + 1] = lg[i][j] + 1;
			else lg[i + 1][j + 1] = max(lg[i][j + 1], lg[i + 1][j]);
		}
	cout << lg[n][m] << endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int q;
    cin >> q;
    for(int count = 0; count < q; count++){
        string str_x, str_y;
        cin >> str_x;
        cin >> str_y;
        int length_x, length_y;
        length_x = str_x.size();
        length_y = str_y.size();
        
        vector<vector<int>> common;
        common.resize(length_x+1);
        for(int x = 0; x <= length_x; x++){
            common[x].resize(length_y+1);
        }
        
        for(int x = 0; x <= length_x; x++){
            common[x][0] = 0;
        }
        for(int y = 0; y <= length_y; y++){
            common[0][y] = 0;
        }
        for(int x = 1; x <= length_x; x++){
            for(int y = 1; y <= length_y; y++){
                if(str_x[x] == str_y[y]){
                    common[x][y] = common[x-1][y-1] + 1;
                } else {
                    if(common[x][y-1] > common[x-1][y]){
                        common[x][y] = common[x][y-1];
                    } else {
                        common[x][y] = common[x-1][y];
                    }
                }
            }
        }
        cout << common[length_x][length_y] << endl;
    }
    return 0;
}