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 <cstring> 
using namespace std;
int c[1001][1001];

int lcs(string x, string y)
{
    int maxl = 0;
    int m = x.length(), n = y.length();
 
    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][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 x,y;
    int q;
    cin>>q;
    while(q--)
    {
        cin>>x>>y;
        int ans = lcs(x, y);
        cout<<ans<<endl;
    }
    return 0;
}

C++: #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
char x[N],y[N];
int c[N][N];
int lcs(char x[],char y[]){

    int lenx = strlen(x+1);
    int leny = strlen(y+1);

    for (int i=0; i<=lenx; i++) {
        c[i][0] = 0;
    }
    for(int j=1;j<=leny;j++){
        c[0][j] = 0;
        
    }

    for(int i=1;i<lenx;i++){
        for(int j=1;j<leny;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]);
        }
    }
    return c[lenx][leny];
}
int main(){
    int q;
    scanf("%d",&q);
    for (int i=0; i<q; i++) {
        cin>>x>>y;
        cout<<lcs(x, y)<<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;
}

C++: #include <iostream>
#include <string>
using namespace std;
int main(void){
   long L[1010][1010]={{0}}, Z; 
   string X, Y; 
   int q;  
    cin >> q; 
  for(int k=0; k<q; k++){ 
      cin >> X;  
      cin >> Y;
      X = ' ' + X;
      Y = ' ' + Y;
      for(int i=1;i<=X.size();i++) L[i][0]=0;
      for(int j=1;j<=Y.size();j++) L[0][j]=0;
      for(int i=1; i<X.size(); i++){
       for(int j=1; j<Y.size(); j++){
           if(X[i] == Y[j])
                L[i][j]=1+L[i-1][j-1];
           else L[i][j]=max(L[i][j-1], L[i-1][j]); 
          Z=L[i][j];
       } 
     } 
     cout << Z << endl;
  }
   return 0;
}

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

using namespace std;

typedef pair<int,int> pii;

vector<pii> P;

string s,t,rev;

const int MAX_N = 10001;

int dp[MAX_N][MAX_N];

void trace(int i,int j){
	if(dp[i][j] == dp[i-1][j] && dp[i][j] == dp[i][j-1]){
		trace(i-1,j-1);	//??????????§????
	}else if(dp[i][j] == dp[i-1][j]){
		trace(i-1,j);	//???????§????
	}else if(dp[i][j] == dp[i][j-1]){
		trace(i,j-1);	//???????§????
	}else{
		rev += s[i-1];
		if(dp[i-1][j-1] == 0){
			return;
		}
		trace(i-1,j-1);	//??????????§????
	}
}
int main()
{
	string com;
	int n;
	cin >> n;
	for(int l=0;l<n;l++){
	cin >> s;
	cin >> t;
	for(int i=0;i<=s.length();i++){
		dp[i][0] = 0;
	}
	for(int i=0;i<=t.length();i++){
		dp[0][i] = 0;
	}
	for(int i=1;i<=s.length();i++){
		for(int j=1;j<=t.length();j++){
			if(s[i] == t[j]){
				dp[i][j] = dp[i-1][j-1]+1;
			}else{
				dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
			}
		}
	}
	printf("%d\n",dp[s.length()][t.length()]);
	}
	/*
	trace(s.length(),t.length());
	for(int i=rev.length();i>0;i--){
		com += rev[i-1];
	}
	cout << com << "\n";	//????????±?????¨???????????????????????????
	*/
}

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

int main(void){
    int L[1010][1010], Z;
    string X, Y;
    int q;
    
    cin >> q;
    for(int k=0; k<q; k++){
        cin >> X;
        cin >> Y;
    for(int i=0; i<X.size(); i++){
        for(int j=0; j<Y.size(); j++){
            L[i][j] = 0;
        }
    }
    
    for(int i=0; i<X.size(); i++){
        for(int j=0; j<Y.size(); j++){
            if(i<=0 || j<=0){
                if(X[i]==Y[j])  L[i][j]=1;
                else            L[i][j]=0;
            }
            else if(X[i] == Y[j])    L[i][j]=1+L[i-1][j-1];
            else L[i][j]=max(L[i][j-1], L[i-1][j]);
            Z=L[i][j];
        }
    }
    
    cout << Z << endl;
    
    }
    return 0;
}

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

const int MAX = 1000;
static int n, m;
static char S[150][MAX], T[150][MAX];
static int ans[150][MAX];
void solve(int in)
{
	int count_max = 0;
	for (int i = n - 1; i >= 0; i--) {
		count_max = 0;
		for (int j = n - 1; j >= 0; j--) {
			int count = 0;
			int tem_i = i, tem_j = j;
			//?????´??????????????????????????????????????´????????´????????¢?´¢??????
			if (S[in][tem_i] == T[in][tem_j] && S[in][tem_i + 1] == T[in][tem_j + 1] && tem_i + 1 < n && tem_j + 1 < m)
				break;
			while (S[in][tem_i] == T[in][tem_j]&& tem_i>=0 && tem_j>=0 ) {
				count++;
				tem_i--;
				tem_j--;
			}
			if (count_max < count) {
				count_max = count;
			}
		}
		ans[in][i] = count_max;
		//???????????§??§i??????????????§?????¨??????????±???????.
	}
}
int main()
{
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> S[i];
		cin >> T[i];
		n = (int)strlen(S[i]);
		m = (int)strlen(T[i]);
		solve(i);
	}

	for (int i = 0; i < q; i++)
	cout << *max_element(&ans[i][0], &ans[i][n]) << endl;

	return 0;
}

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