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++: //JOI 0528 Common Sub-String
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	while(1){
		string s, t; int roop1=0, save=0, ans = 0;
		cin>>s;
		cin>>t;
		if(s==\0){
		break;
		}
	for (int i = 0; i<s.size(); i++){
		for (int j = 0; j<t.size(); j++){
			if (s[i] == t[j]){
				roop1 = 0;
				save= 0;
				while (1){
					if (s[i + roop1] == 0 || t[j + roop1] == 0){
						break;
					}
					else{
						if (s[i + roop1] == t[j + roop1]){
							save += 1;
							roop1++;
						}
					else if (s[i + roop1] != t[j + roop1]){
							ans=max(ans,save);
							break;
						}
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	}
	
	return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S, T;

    while(cin >> S >> T) {
        int ans = 0;
        int i = 0, j = 0;
        rep(k, 2) {
            rep(i, S.length()) {
                int tmp = 0;
                rep(j, S.length()) {
                    if (i + j == S.length()) break;
                    if (S[i+j] == T[j]) tmp++;
                    else tmp = 0;
                    ans = max(ans, tmp);
                }
                //dump(ans);
            }
            swap(S, T);
        }
        cout << ans << endl;
    }


    return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define rep(I,N) for(int I = 0; I < (int)(N); I++)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[12] = {2, 2, 2, 1, 0, -1, -2, -2, -2, -1, 0, 1};
int dy[12] = {1, 0, -1, -2, -2, -2, -1, 0, 1, 2, 2, 2};
int main(void){
	int px, py, N;
	while(cin >> px >> py && (px||py)){
		int pyon = (9*py+px);
		cin >> N;
		int spr[11];
		rep(i, N){
			int a, b;
			cin >> a >> b;
			spr[i] = (9*b)+a;
		}
		if(N == 0){
			FIN("NA");
			continue;
		}
		bool flag = false;
		queue<P> que;
		que.push(P(pyon, 0));
		while(!que.empty()){
			P p = que.front();
			int x = p.first%9;
			int y = p.first/9;
			int spX = spr[p.second]%9;
			int spY = spr[p.second]/9;
			que.pop();
			if(p.second == N){
				//FIN(x);
				//FIN(y);
				flag = true;
				break;
			}
			rep(i, 12){
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx >= 0 && nx < 10 && ny >= 0 && ny < 10){
					if( (spX + 1) >= nx && (spY + 1) >= ny && (spX - 1) <= nx && (spY - 1) <= ny){
						que.push(P(((9*ny)+nx), p.second+1));
					}
				}
			}
		}
		cout << (flag?"OK":"NA") << endl;
	}
	return 0;
}



int StrToInt(string s){
	stringstream ss;
	ss << s;
	int val;
	ss >> val;
	return val;
}
string IntToStr(int i){
	stringstream ss;
	ss << i;
	return ss.str();
}

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

const int NMAX = 4008;

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 += '\0' + 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 <bits/stdc++.h>
using namespace std;

int main()
{
	string s, t;
	while (cin >> s) {
		cin >> t;
		int n = s.size(), m = t.size(), res = 0;
		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 (s[i] == t[j]) {
					dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
					res = max(res, dp[i + 1][j + 1]);
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<string>
using namespace std;
char a[20000];
int main(){
	string c,d;
	while(cin>>c>>d){
	for(int i=0;i<20000;i++)
		a[i]='-';
	for(int i=0;i<c.size();i++)
		a[i+10000]=c[i];
	int ans=0;
	for(int first=0;first<20000-d.size();first++){
		int count=0;
		for(int j=0;j<d.size();j++){
			if(a[first+j]==d[j])
				count++;
			else{
				ans=max(ans,count);
				count=0;
			}
		}
	}
	cout<<ans<<endl;
	}
	return 0;
}

C++: //JOI 0528 Common Sub-String
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	string s, t; int roop1, roop2 = 0, save[10000], ans = 0;
	while(cin>>s>>t){
	for (int i = 0; i<s.size(); i++){
		for (int j = 0; j<t.size(); j++){
			if (s[i] == t[j]){
				roop1 = 0;
				save[roop2] = 0;
				while (1){
					if (s[i + roop1] == 0 || t[j + roop1] == 0){
						break;
					}
					else{
						if (s[i + roop1] == t[j + roop1]){
							save[roop2] += 1;
							roop1++;
						}
						else if (s[i + roop1] != t[j + roop1]){
							roop2++;
							break;
						}
					}
				}
			}
		}
	}
	sort(save, save + roop2 + 1);
	ans = save[roop2];
	cout << ans << endl;
	}
	return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char s[4001],t[4001];
int l,r;
bool C(int x){
  for(int i=0;i+x<=l;i++){
    if(search(t,t+r,s+i,s+i+x)!=t+r){
      return true;
    }
  }
  return false;
}

int main(){
  while(true){
    if(scanf("%s %s",s,t)==EOF) return 0;
    l = strlen(s), r = strlen(t);
    int lb = 0, ub = min(l,r) + 1;
    while(ub - lb > 1){
      int mid = (ub + lb) / 2;
      if(C(mid)) lb = mid;
      else ub = mid;
    }
    printf("%d\n",lb);
  }
}