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
var dp [4001][4001]int

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()

		for i := range dp {
			for j := range dp[i] {
				dp[i][j] = 0
			}
		}

		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++: #include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class SuffixArray {
	void CEB(vector<int> &v, vector<int> &b) {
		int vs = v.size(), bs = b.size();
		fill(b.begin(), b.end(), 0);
		for (int i = 0; i < vs; i++) b[v[i]]++;
		for (int i = 1; i < bs; i++) b[i] += b[i - 1];
	}
	void ISort(vector<int> &v, vector<int> &SA, int mv, vector<int> &b, vector<int> &isL) {
		int vs = v.size(), bs = b.size();
		fill(b.begin(), b.end(), 0);
		for (int i = 0; i < vs; i++) b[v[i]]++;
		int sum = 0;
		for (int i = 0; i < bs; i++) b[i] += sum, swap(sum, b[i]);
		for (int i = 0; i < vs; i++) {
			if (SA[i] > 0 && isL[SA[i] - 1]) SA[b[v[SA[i] - 1]]++] = SA[i] - 1;
		}
	}
	void IISort(vector<int> &v, vector<int> &SA, int mv, vector<int> &b, vector<int> &isL) {
		CEB(v, b);
		for (int i = v.size() - 1; i >= 0; i--) {
			if (SA[i] > 0 && !isL[SA[i] - 1]) SA[--b[v[SA[i] - 1]]] = SA[i] - 1;
		}
	}
	vector<int>SA_IS(vector<int> v, int mv) {
		int vs = v.size();
		if (vs == 1) return vector<int>(1, 0);
		vector<int> isL(vs), b(mv + 1), SA(vs, -1), ord(vs);
		auto isLMS = [&](int x)->bool { return x > 0 && isL[x - 1] && !isL[x]; };
		for (int i = vs - 2; i >= 0; i--) isL[i] = (v[i] > v[i + 1]) || (v[i] == v[i + 1] && isL[i + 1]);
		CEB(v, b);
		for (int i = 0; i < vs; i++) {
			if (isLMS(i)) SA[--b[v[i]]] = i;
		}
		ISort(v, SA, mv, b, isL);
		IISort(v, SA, mv, b, isL);
		int cur = 0;
		for (int i = 0; i < vs; i++) {
			if (isLMS(i)) ord[i] = cur++;
		}
		vector<int> nxv(cur);
		cur = -1;
		int prev = -1;
		for (int i = 0; i < vs; i++) {
			if (!isLMS(SA[i])) continue;
			bool diff = false;
			for (int d = 0; d < vs; d++) {
				if (prev == -1 || v[SA[i] + d] != v[prev + d] || isL[SA[i] + d] != isL[prev + d]) {
					diff = true;
					break;
				}
				else if (d && isLMS(SA[i] + d))break;
			}
			if (diff) cur++, prev = SA[i];
			nxv[ord[SA[i]]] = cur;
		}
		vector<int> reord(nxv.size());
		for (int i = 0; i < vs; i++) {
			if (isLMS(i)) reord[ord[i]] = i;
		}
		vector<int> nxSA = SA_IS(nxv, cur);
		CEB(v, b);
		for (int i = 0; i < SA.size(); i++) SA[i] = -1;
		for (int i = nxSA.size() - 1; i >= 0; i--) {
			SA[--b[v[reord[nxSA[i]]]]] = reord[nxSA[i]];
		}
		ISort(v, SA, mv, b, isL);
		IISort(v, SA, mv, b, isL);
		return SA;
	}
	vector<int>SA_IS(string s) {
		vector<int> v(s.size() + 1);
		for (int i = 0; i < s.size(); i++) v[i] = s[i] + 1;
		return SA_IS(v, *max_element(v.begin(), v.end()));
	}
	vector<int>construct_lcp(string &s, vector<int> &sa) {
		vector<int> lcp, rank(s.size() + 1);
		int n = s.size(), h = 0;
		for (int i = 0; i <= n; i++) rank[sa[i]] = i;
		for (int i = 0; i < n; i++) {
			int j = sa[rank[i] - 1];
			if (h) h--;
			for (; j + h < n && i + h < n; h++) {
				if (s[j + h] != s[i + h]) break;
			}
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
public:
	string s;
	vector<int> sa, lcp;
	void init(string &T) {
		s = T;
		sa = SA_IS(s);
		lcp = construct_lcp(s, sa);
	}
	SuffixArray(string &t) { init(t); }
	SuffixArray() {}
	bool contain(string &t) {
		int a = 0, b = s.size();
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (s.compare(sa[c], t.size(), t) < 0) a = c;
			else b = c;
		}
		return s.compare(sa[b], t.size(), t) == 0;
	}
};
string s, t;
int main() {
	while(cin >> s >> t) {
		int sl = s.size(); s += '$' + t;
		SuffixArray v(s);
		int ret = 0, e = s.size() + t.size() + 1;
		for(int i = 0; i < e; i++) {
			if((v.sa[i] < sl) != (v.sa[i + 1] < sl)) ret = max(ret, v.lcp[i]);
		}
		cout << ret << endl;
	}
}

C++: #include<bits/stdc++.h>
#define LL long long
#define rep(a,b) for(int a=0;a<b;a++)
#define pb push_back
#define str string
#define INF 100000000
using namespace std;
LL sub_string(const string& s1,const string& s2,LL l1,LL l2){
    LL len=min(s1.size()-l1,s2.size()-l2);
    LL lon=0;
    LL ans=0;
    for(int j=0;j<len;j++){
        if(s1[l1+j]==s2[l2+j]){
            lon++;
        }else{
            ans=max(ans,lon);
        }
    }return max(ans,lon);
}
int main(){
    str s1,s2;
    LL ans=0;
    int i=0;
    while(1){
    cin >> s1 >> s2;
    if(s1=="EOF")break;
    LL l1=s1.size();
    LL l2=0;
        while(l1!=0||l2<=s2.size()){
            if(l1!=0){
                l1--;
            }else{
                l2++;
            }
            ans=max(ans,sub_string(s1,s2,l1,l2));
        }
        cout << ans << endl;
        if(i==9){
            break;
        }else{
            i++;
        }
    }
return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int main(){
  string s1,s2;
  vector<int> cmap[256];
  while(cin >> s1){
    cin >> s2;
    if(s1.size() > s2.size()) swap(s1,s2);
    s1+="~";
    s2+=".";
    for(int i=0;i<(int)s2.size();i++){
      cmap[s2[i]].push_back(i);
    }
    int res=0;
    for(int i=0;i<(int)s1.size();i++){
      if(cmap[s1[i]].empty()) continue;
      for(int j=0;j<(int)cmap[s1[i]].size();j++){
	int id = cmap[s1[i]][j];
	int k=1;
	if(res > s2.size()-1-id) break;
	while(s1[i+k] == s2[id+k]) k++;
	res = max(res,k);
      }
    }
    printf("%d\n",res);
    for(int i=0;i<256;i++) cmap[i].clear();
  }
}

C++: #include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
int INF=1e9;
int MOD=1000000007;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
double EPS = 1e-10;
const int mod=1e9+7;
int dp[4000][4000];
int main(){
  string s,t;
  cin>>s>>t;
  int ans=0;
  REP(i,s.size()){
    REP(j,t.size()){
      if(s[i]==t[j]){
        if(i==0||j==0)dp[i][j]=1;
        else dp[i][j]=dp[i-1][j-1]+1;
      }
      ans=max(ans,dp[i][j]);
    }
  }
  cout<<ans<<endl;
}

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

int main(){
  string str1,str2;
  while(cin >> str1){
    cin >> str2;
    int cnt[4100][4100];
    int len1 = str1.size();
    int len2 = str2.size();
    str1 = ' ' + str1;
    str2 = ' ' + str2;
    for(int i=1;i<=len1;i++){
      cnt[i][0] = 0;
    } 
    for(int i=1;i<=len2;i++){
      cnt[0][i] = 0;
    }
    int ret = 0;
    for(int i=1;i<=len1;i++){
      for(int j=1;j<=len2;j++){
	if(str1[i] == str2[j]){
	  cnt[i][j] = cnt[i-1][j-1] + 1;
	}
	else {
	  cnt[i][j] = 0;
	}
	ret = max(ret,cnt[i][j]);
      }
    }
    cout << ret << endl;
  }	
}

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

using namespace std;

int func(string s1, string s2)
{
	int m = 0, t;
	
	for(int i = 0; i < s1.size(); i++){
		for(int j = 0; j < s2.size() && j+i < s1.size(); j++){
			if(s1[i+j] == s2[j]){
				t = 1;
				j++;
				while(i+j < s1.size() && j < s2.size() && s1[i+j] == s2[j]){
					j++;
					t++;
				}
				m = max(m, t);
			}
		}
	}
	
	return m;
}

int main()
{
	string s1, s2;
	
	while(cin>>s1>>s2){
		cout << max(func(s1, s2), func(s2, s1))	<< endl;
	}
	
	return 0;
}