// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0528
#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/string/suffix-array.hpp"
#include <iostream>
std::string S, T;
inline void solve(void) {
SuffixArray SA(S + '#' + T);
int n = S.size(), m = T.size(), ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans = std::max(ans, SA.lcp(i, j + n + 1));
}
}
std::cout << ans << '\n';
}
int main(int argc, char const *argv[]) {
optimizeIO();
while (std::cin >> S >> T) {
solve();
}
return 0;
}
#line 1 "verify/verify-aizu-string/aizu-suffix-array.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0528
#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>
inline void optimizeIO(void) {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/string/suffix-array.hpp"
#line 7 "src/alfred/string/suffix-array.hpp"
#line 1 "src/alfred/data_structure/sparse-table.hpp"
#line 7 "src/alfred/data_structure/sparse-table.hpp"
template <class T>
struct MaxInfo {
T val;
MaxInfo(void) { val = std::numeric_limits<T>::min(); }
template <class InitT>
MaxInfo(InitT x) { val = x; }
MaxInfo operator+(MaxInfo &x) {
return {std::max(val, x.val)};
}
};
template <class T>
struct MinInfo {
T val;
MinInfo(void) { val = std::numeric_limits<T>::max(); }
template <class InitT>
MinInfo(InitT x) { val = x; }
MinInfo operator+(MinInfo &x) {
return {std::min(val, x.val)};
}
};
template <class T>
struct GcdInfo {
T val;
GcdInfo(void) { val = T(); }
template <class InitT>
GcdInfo(InitT x) { val = x; }
GcdInfo operator+(GcdInfo &x) {
#if __cplusplus >= 201703L
return {std::gcd(x.val, val)};
#else
return {__gcd(x.val, val)};
#endif
}
};
template <class T>
class SparseTable {
private:
int n;
std::vector<std::vector<T>> ST;
public:
SparseTable(void) {}
SparseTable(int N) : n(N), ST(N, std::vector<T>(std::__lg(N) + 1)) {}
template <class InitT>
SparseTable(std::vector<InitT> &_init) : SparseTable(_init.size()) { init(_init, true); }
template <class InitT>
inline void init(std::vector<InitT> &_init, bool internal = false) {
if (!internal) {
n = _init.size();
ST.assign(n, std::vector<T>(std::__lg(n) + 1));
}
for (int i = 0; i < n; i++) ST[i][0] = T(_init[i]);
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
ST[j][i] = ST[j][i - 1] + ST[j + (1 << (i - 1))][i - 1];
}
}
}
inline T query(int l, int r) { // 0 based
if (l > r) return T();
int w = std::__lg(r - l + 1);
return ST[l][w] + ST[r - (1 << w) + 1][w];
}
inline T disjoint_query(int l, int r) {
if (l > r) return T();
T ans = T();
for (int i = std::__lg(r - l + 1); i >= 0; i--) {
if ((1 << i) <= r - l + 1) {
ans = ans + ST[l][i];
l += 1 << i;
}
}
return ans;
}
};
#line 9 "src/alfred/string/suffix-array.hpp"
class SuffixArray {
private:
int n;
std::string s; // internal is 1-index, access is 0-indexed.
SparseTable<MinInfo<int>> ST;
std::vector<int> sa, rnk, old, h;
public:
SuffixArray(std::string S) : n(S.size()), s(S) {
const int m = n + 1;
s.insert(s.begin(), ' '), sa.assign(m, 0);
rnk.assign(m, 0), old.assign(m, 0), h.assign(m, 0);
for (int i = 1; i <= n; i++) sa[i] = i, rnk[i] = s[i];
for (int w = 1; w < n; w *= 2) {
std::copy(rnk.begin(), rnk.end(), old.begin());
auto cmp = [&](int x, int y) {
if (old[x] != old[y]) return old[x] < old[y];
if (y + w > n) return false;
if (x + w > n) return true;
return old[x + w] < old[y + w];
};
std::sort(std::next(sa.begin()), sa.end(), cmp);
for (int i = 1; i <= n; i++) {
rnk[sa[i]] = rnk[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
}
if (rnk[sa[n]] == n) break;
}
for (int i = 1, k = 0; i <= n; i++) {
if (rnk[i] == 0) continue;
if (k != 0) k--;
while (std::max(i, sa[rnk[i] - 1]) <= n - k &&
s[i + k] == s[sa[rnk[i] - 1] + k]) {
k++;
}
h[rnk[i]] = k;
}
ST.init(h);
}
const std::vector<int> get_h(void) { return h; }
const std::vector<int> get_sa(void) { return sa; }
const std::vector<int> get_rnk(void) { return rnk; }
inline int lcp(int i, int j) { // 0-indexed !
i = rnk[i + 1], j = rnk[j + 1];
if (i > j) std::swap(i, j);
return i == j ? n - i : ST.query(i + 1, j).val;
}
};
#line 6 "verify/verify-aizu-string/aizu-suffix-array.test.cpp"
std::string S, T;
inline void solve(void) {
SuffixArray SA(S + '#' + T);
int n = S.size(), m = T.size(), ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans = std::max(ans, SA.lcp(i, j + n + 1));
}
}
std::cout << ans << '\n';
}
int main(int argc, char const *argv[]) {
optimizeIO();
while (std::cin >> S >> T) {
solve();
}
return 0;
}
verify/verify-aizu-string/aizu-suffix-array.test.cpp