Competitive-Programming/template/SA.cpp at master · HanaYukii/Competitive-Programming · GitHub

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// Suffix Array
// cses 2106
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 200005;
void count_sort(vector<int>&p, vector<int>&c) {
    int n = p.size();
    vector<int>cnt(n);
    for (auto &i : c) {
        cnt[i]++;
    }
    vector<int>p_new(n);
    vector<int>pre{0};
    for (auto &i : cnt) {
        pre.push_back(pre.back() + i);
    }
    for (auto &i : p) {
        p_new[pre[c[i]]++] = i;
    }
    p = p_new;
}
void go() {
    int n;
    string s;
    cin >> s;
    s += '$';
    n = s.size();
    vector<int>c(n), p(n);
    {
        vector<pair<char,int>>a(n);
        for (int i = 0 ; i < n ; i++) {
            a[i] = {s[i], i};
        }
        sort((a).begin(), (a).end());
        for (int i = 0 ; i < n ; i++) {
            p[i] = a[i].second;
        }
        c[p[0]] = 0;
        for (int i = 1 ; i < n ; i++) {
            if (a[i].first == a[i - 1].first) {
                c[p[i]] = c[p[i - 1]];
            }
            else {
                c[p[i]] = c[p[i - 1]] + 1;
            }
        }
    }
    int k = 0;
    while ((1 << k) < n) {
        for (int i = 0 ; i < n ; i++) {
            p[i] = (p[i] - (1 << k) + n) % n;
        }
        count_sort(p, c);
        vector<int>c_new(n);
        c_new[p[0]] = 0;
        for (int i = 1 ; i < n ; i++) {
            pair<int,int> cur = {c[p[i]], c[(p[i] + (1 << k)) % n]};
            pair<int,int> prev = {c[p[i-1]], c[(p[i - 1] + (1 << k)) % n]};
            if (cur == prev) {
                c_new[p[i]] = c_new[p[i - 1]];
            }
            else {
                c_new[p[i]] = c_new[p[i - 1]] + 1;
            }
        }
        c = c_new;
        k++;
    }
    int lcp[s.size()] = {};
    k = 0;
    for (int i = 0 ; i < n - 1 ; i++) {
        int pos = c[i];
        int j = p[pos-1];
        while (s[i + k] == s[j + k]) {
            k++;
        }
        lcp[c[i]-1] = k;
        k = max(k - 1, 0);
    }
    int mx = 0;
    for (int i = 0; i < (int)s.size() - 1; i++) {
        if  (lcp[i] > lcp[mx]) {
            mx = i;
        }
    }
    if (lcp[mx] == 0) {
        cout << -1 << '\n';
    }
    else {
        cout << s.substr(p[mx], lcp[mx]) << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }
}