1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int sa[N], rk[N], cnt[N], oldrk[N << 1], id[N], px[N];
string s;
int ht[N];
int f[N][2];
inline bool cmp(int x, int y, int k) {
return oldrk[x] == oldrk[y] && oldrk[x + k] == oldrk[y + k];
}
void SA(){
int i, p = 0, k, m = 300;
memset(cnt, 0, sizeof cnt);
for (i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
for (k = 1; k < n; k <<= 1, m = p) {
for (p = 0, i = n ; i > n - k; i--) id[++p] = i;
for (i = 1;i <= n; i++){
if (sa[i] > k) id[++p] = sa[i] - k;
}
// memset(cnt, 0, sizeof cnt);
for (i = 0; i <= m; i++) cnt[i] = 0;
for (i = 1; i <= n; i++) cnt[px[i] = rk[id[i]]]++;
for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; i--) sa[cnt[px[i]]--] = id[i];
memcpy(oldrk, rk, sizeof rk);
for (p = 0, i = 1; i <= n; i++) {
rk[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
}
}
for (int i = 1; i <= n; i++) {
if (rk[i] == 1) continue;
int k = max(ht[rk[i - 1]] - 1, 0);
while (i + k <= n && s[i + k]== s[sa[rk[i] - 1] + k]) k++;
ht[rk[i]] = k;
}
}
bool check(int len) {
int ans = 0;
for (int i = 1; i <= n; i++) {
if (ht[i] < len) continue;
int j = i;
while (j + 1 <= n && ht[j + 1] >= len) j++;
ans = max(ans, j - i + 2);
i = j;
}
if (ans >= 2) {
printf("%d\n", ans);
return true;
}
return false;
}
void solve() {
int len = 1;
while (check(len)) len++;
puts("");
}
int main() {
string line;
while (getline(cin, line)) {
stringstream ss(line);
n = 0;
s = "#";
string t;
while (ss >> t) {
s += t;
n += t.size();
}
if (s.size() < 2) break;
SA();
solve();
}
return 0;
}
|