Go: ///
// File:  0528.go
// Author: ymiyamoto
//
// Created on Thu Mar 22 01:52:09 2018
//
package main

import (
	"bufio"
	"fmt"
	"os"
)

var S, T string

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for {
		scanner.Scan()
		S = scanner.Text()
		if len(S) == 0 {
			return
		}

		scanner.Scan()
		T = scanner.Text()

		dp := make([][]int, len(S)+1)
		for i := range dp {
			dp[i] = make([]int, len(T)+1)
		}

		dp[0][0] = 0
		for i := range S {
			for j := range T {
				if S[i] == T[j] {
					dp[i+1][j+1] = max(dp[i+1][j], max(dp[i][j+1], dp[i][j]+1))
				} else {
					dp[i+1][j+1] = 0
				}
			}
		}
		var m int
		for i := range dp {
			for j := range dp[i] {
				m = max(m, dp[i][j])
			}
		}
		fmt.Println(m)
	}
}

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

const int NMAX = 20000;

int n, k;
int Rank[NMAX + 1];
int tmp[NMAX + 1];

bool compare_sa(int i, int j) {
  if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];
  else {
    int ri = i + k <= n ? Rank[i + k] : -1;
    int rj = j + k <= n ? Rank[j + k] : -1;
    return ri < rj;
  }
}

void construct_sa(string S, int *sa) {
  n = S.length();

  for (int i = 0; i <= n; i++) {
    sa[i] = i;
    Rank[i] = i < n ? S[i] : -1;
  }

  for (k = 1; k <= n; k *= 2) {
    sort(sa, sa + n + 1, compare_sa);

    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + 
        (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
    }

    for (int i = 0; i <= n; i++) {
      Rank[i] = tmp[i];
    }
  }
}

void construct_lcp(string S, int *sa, int *lcp) {
  int n = S.length();
  for (int i = 0; i <= n; i++) Rank[sa[i]] = i;

  int h = 0;
  lcp[0] = 0;
  for (int i = 0; i < n; i++) {
    int j = sa[Rank[i] - 1];

    if (h > 0) h--;
    for (; j + h < n and i + h < n; h++) {
      if (S[j + h] != S[i + h]) break;
    }

    lcp[Rank[i] - 1] = h;
  }
}

string S, T;

const int LMAX = 4008;
int sa[LMAX], lcp[LMAX];

int solve() {
  int sl = S.length();
  S += '_' + T;

  construct_sa(S, sa);
  construct_lcp(S, sa, lcp);

  int ans = 0;
  for (int i = 0; i < S.length(); i++) {
    if ((sa[i] < sl) != (sa[i + 1] < sl)) {
      ans = max(ans,lcp[i]);
    }
  }
  return ans;
}

int main() {
  while (cin >> S >> T) {
    cout << solve() << endl;
  }
}

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

int main() {
    string s, t;
    while (cin >> s >> t) {
        int dp[s.size()][t.size()];
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < t.size(); j++) {
                if (s[i] == t[j]) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        for (int i = 1; i < s.size(); i++) {
            for (int j = 1; j < t.size(); j++) {
                if (dp[i][j]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < t.size(); j++) {
                ans = max(ans, dp[i][j]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C++: #include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;

int dp[4000][4000];
char s[4001], t[4001];

int main() {
    while (cin >> s >> t) {
        for (int j = 0; j < 4000; ++j) {
            fill(dp[j], dp[j] + 4000, 0);
        }

        int sLen = strlen(s);
        int tLen = strlen(t);

        int ret = 0;

        for (int j = 0; j < sLen; ++j) {
            for (int k = 0; k < tLen; ++k) {
                if (s[j] != t[k]) {
                    dp[j][k] = 0;
                } else if (j == 0 || k == 0) {
                    dp[j][k] = 1;
                } else {
                    dp[j][k] = dp[j-1][k-1] + 1;
                }

                ret = max(ret, dp[j][k]);
            }
        }

        cout << ret << endl;
    }
    return 0;
}

C++: class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
for(;sc.hasNext();){
String s=sc.next();
String t=sc.next();
System.out.println(lcs(s,t).length());
}
}

	static String lcs(String s, String t){
		int m=s.length(), n=t.length();
		int[][] d=new int[n+1][m+1];
		int[][] v=new int[n+1][m+1];
		for(int j=1; j<=n; j++){
			for(int i=1; i<=m; i++){
				if(s.charAt(i-1)==t.charAt(j-1)){
					d[j][i]=d[j-1][i-1]+1;
					v[j][i]=0;
				}else if(d[j][i-1]>d[j-1][i]){
					d[j][i]=d[j][i-1];
					v[j][i]=+1;
				}else{
					d[j][i]=d[j-1][i];
					v[j][i]=-1;
				}
			}
		}
		String r="";
		for(int i=m, j=n; i>0&&j>0;){
			debug(i, j);
			if(v[j][i]>0)
				i--;
			else if(v[j][i]<0)
				j--;
			else{
				r=s.charAt(i-1)+r;
				i--;
				j--;
			}
		}
		return r;
	}

}

C++: #include<bits/stdc++.h>
using namespace std;
int ans,s1,s2;
int solve(int tt,int pp);
string text,patn;

int main(){

    while(cin >> text){
        cin >> patn;
        s1=text.size();
        s2=0;
        ans=0;
        while(s1!=0 || s2<=(int)patn.size()){
            if(s1!=0)s1--;
            else s2++;
            ans=max(ans,solve(s1,s2));
            }
        cout << ans << endl;
        ans=0;
    }
    return 0;
}

int solve(int tl,int pl){
    int tt=0;
    int pp=0;
    int len=min(text.size()-tl,patn.size()-pl);
    for(int i=0;i<len;i++){
        if(text[tl+i]==patn[pl+i]){
            tt++;
        }else{
            pp=max(pp,tt);
            tt=0;
        }
    }
    return max(pp,tt);
}

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

using namespace std;

string s,t;
long long m=1,dp[4000][4000];

void solve(){
    for(int i=0;i<s.size();i++){
        for(int j=0;j<t.size();j++){
            if(s[i]==t[j]){m++;
                dp[i+1][j+1]=dp[i][j]+1;
            }else{
                dp[i+m][j+m]=(dp[i][j+m],dp[i+m][j]);
            m=1;
            }
        }
    }
cout << dp[s.size()][t.size()] << endl;
}


int main(){
while(1){
cin >> s >>t;
if(s=="EOF")break;
solve();
}
//cout << s.size();
return 0;
}

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

using namespace std;

string s,t;
long long dp[4001][4001];

void solve(){
    for(int i=0;i<s.size();i++){
        for(int j=0;j<t.size();j++){
            if(s[i]==t[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }else{
                dp[i+1][j+1]=(dp[i][j+1]>dp[i+1][j])?dp[i][j+1]:dp[i+1][j];
            }
        }
    }
cout << dp[s.size()][t.size()] << endl;
}


int main(){
while(1){
cin >> s >>t;
if(s=="EOF")break;
solve();
}
return 0;
}

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

std::string s1,s2;

int dp[4001][4001];

int main() {
    
    while(1) {
        
        if(std::cin.eof())
            break;
        
        std::memset(dp,0,sizeof(dp));
        
        std::cin>>s1>>s2;
        
        for(int i=1;i<=s1.size();++i){
            for(int j=1;j<=s2.size();++j){
                if(s1[i-1]==s2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
            }
        }
        
        int ans=0;
        
        for(int i=1;i<=s1.size();++i){
            for(int j=1;j<=s2.size();++j){
                ans=std::max(ans,dp[i][j]);
            }
        }
        
        std::cout<<ans<<std::endl;
    }
    
    return 0;
}