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 <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], h, w;
    scanf("%s", x);
    scanf("%s", y);
    h = strlen(x), w = strlen(y);
    int dp[h][w], len[w];
    rep(j, h) rep(k, w) dp[j][k] = 0;
    rep(j, w) if(x[0] == y[j]) dp[0][j] = 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;
      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");
    }*/
    int maxs = 0;
    rep(j, w) if(maxs < dp[h - 1][j]) maxs = dp[h - 1][j];
    printf("%d\n", maxs);
  }
  return 0;
}

C++: #include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
bool isSubstring(string substr, string t) {
	int n = substr.length();
	int seek = 0;
	rep(i, n) {
		bool ex = 0;
		for (int j = seek; j < t.length(); j++) {
			if (substr[i] == t[j]) {
				ex = 1;
				seek = j + 1;
				break;
			}
		}
		if (ex) {
			continue;
		}
		else {
			return false;
		}
	}
	return true;

}

int LongestCommonSubstring(string s, string t) {
	vector<int>dp(s.length(), 0);
	int n = s.length();
	string lcs = "";
	if (isSubstring(s.substr(n - 1, n), t)) {

		dp[n - 1] = 1;
		lcs = s[n - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		//string substr = s.substr(i, n);
		string substr = s[i] + lcs;
		int issubst = isSubstring(substr, t);
		if (issubst) lcs = substr;
		dp[i] = dp[i + 1] + issubst;
	}
	return dp[0];
}
int main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring("bacd", "becd") << endl;
	//cout << LongestCommonSubstring("abcd", "becd") << endl;
	int q;
	cin >> q;
	vector<string> s(q);
	vector<string> t(q);
	rep(i, q) {
		cin >> s[i] >> t[i];
	}
	rep(i, q) {
		cout << LongestCommonSubstring(s[i], t[i]) << endl;
	}

	return 0;
}

C++: #include <stdint.h>
#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

int dp[1024][1024];

int GetLengthOfLongestCommonSunseq(std::string &a, std::string &b) {
  int max = 0;
  for(int y = 0; y < a.size(); y++){
    for(int x = 0; x < b.size(); x++){
      const int vL = (y > 0) ? dp[y-1][x] : 0;
      const int vU = (x > 0) ? dp[y][x-1] : 0;
      const int vUL = (x > 0 && y > 0) ? dp[y-1][x-1] : 0;
      dp[y][x] = std::max(vL, std::max(vU, vUL + (a[y] == b[x] ? 1 : 0)));
      if(max < dp[y][x]) max = dp[y][x];
    }
  }
  return max;
}

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::string a, b;
    std::cin >> a >> b;
    std::cout << GetLengthOfLongestCommonSunseq(a, b) << std::endl;
  }

  return 0;
}

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

using namespace std;

string s, t;

int main() {
	int n;
	cin >> n;
	while (n--) {
		//dp[i][j] := s???i??????????????§???t???j??????????????§?????£?????¨??????LCS
		vector<vector<int>> dp(200, vector<int>(200));
		cin >> s >> t;
		dp[0][0] = (s[0] == t[0]);
		for (int i = 1; i < s.size(); i++)dp[i][0] = (s[i] == t[0] || dp[i - 1][0]);
		for (int j = 1; j < t.size(); j++)dp[0][j] = (s[0] == t[j] || dp[0][j - 1]);
		
		for (int i = 1; i < s.size(); i++) {
			for (int j = 1; j < t.size(); j++) {
				if (s[i] == t[j])dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])+1;
				else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		cout << dp[s.size() - 1][t.size() - 1] << endl;
	}
}

C++: #include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	int q;
	cin >> q;
	REP(k, q) {
		string X, Y;
		cin >> X >> Y;
		int x = X.size(), y = Y.size();
		vector<vector<int>> dp(x + 1, vector<int>(y + 1));
		REP(i, x) {
			REP(j, y) {
				if (X[i] != Y[j]) {
					dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
				} else {
					dp[i + 1][j + 1] = dp[i][j] + 1;
				}
			}
		}
		cout << dp[x][y] << endl;
	}

	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll q;
  cin >> q;
  while(q--) {
    string s;
    string t;
    cin >> s >> t;
    mat dp(s.size()+1,vec(t.size()+1));
    for(ll i=0;i<s.size();i++) {
      for(ll j=0;j<t.size();j++) {
        if(s[i]==t[j]) {
          dp[i+1][j+1]=max({dp[i][j]+1,dp[i+1][j],dp[i][j+1]});
        }
        else {
          dp[i+1][j+1]=max({dp[i][j],dp[i+1][j],dp[i][j+1]});
        }
      }
    }
    cout << dp[s.size()][t.size()] << endl;
  }
}

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

int Max(int &a,int b){return a=max(a,b);}

int LCS(string &a,string &b){
  int n = a.size();
  int m = b.size();
  vector <vector<int> > dp(n+1,vector<int>(m+1));

  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++){
      if(i<n&&j<m&&a[i] == b[j]) Max(dp[i+1][j+1],dp[i][j]+1);
      Max(dp[i+1][j],dp[i][j]);
      Max(dp[i][j+1],dp[i][j]);
    }
  return dp[n][m];
}

int main(){
  int q;
  cin>>q;
  while(q--){
    string a,b;
    cin>>a>>b;
    cout<<LCS(a,b)<<endl;
  }
  return 0;
}