template/Suffix Array.cpp at main · sazid62/template · 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n';


#define M 10007

const int kinds = 256;
char str[M];
char s[M];
int K, buc[M], r[M], sa[M], X[M], Y[M], high[M];
bool cmp(int *r, int a, int b, int x)
{
    return (r[a] == r[b] && r[a + x] == r[b + x]);
}
vector<int>suffix;
int lcp[M];

void suffix_array_DA(int n, int m)
{
    int *x = X, *y = Y, i, j, k = 0, l;
    memset(buc, 0, sizeof(buc));
    for (i = 0; i < n; i++)
        buc[ x[i] = str[i] ]++;
    for (i = 1; i < m; i++)
        buc[i] += buc[i - 1];
    for (i = n - 1; i >= 0; i--)
        sa[--buc[x[i]]] = i;
    for (l = 1, j = 1; j < n; m = j, l <<= 1)
    {
        j = 0;
        for (i = n - l; i < n; i++)
            y[j++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= l)
                y[j++] = sa[i] - l;
        for (i = 0; i < m; i++)
            buc[i] = 0;
        for (i = 0; i < n; i++)
            buc[ x[y[i]] ]++;
        for (i = 1; i < m; i++)
            buc[i] += buc[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[ --buc[ x[y[i]] ]] = y[i];
        for (swap(x, y), x[sa[0]] = 0, i = 1, j = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], l) ? j - 1 : j++;
    }
    for (i = 1; i < n; i++)
        r[sa[i]] = i;
    for (i = 0; i < n - 1; high[r[i++]] = k)
        for (k ? k-- : 0, j = sa[r[i] - 1]; str[i + k] == str[j + k]; k++);
}
void suffix_array_construction(char s[])
{
    int n = strlen(s);
    for (int i = 0; i < n; i++)
        str[i] = s[i];
    str[n] = '\0';
    suffix_array_DA(n + 1, kinds);

    for (int i = 1; i <= n; i++)
        suffix.push_back(sa[i]);
}
void lcp_construction(char const s[], vector<int> const& p)
{
    int n = strlen(s);
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;
    int k = 0;

    for (int i = 0; i < n; i++)
    {
        if (rank[i] == n - 1)
        {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
}


void build() {
    suffix_array_construction(s);
    lcp_construction(s, suffix);
}

void clear() {
    int n = strlen(s);
    for (int i = 0; i < n; i++) lcp[i] = 0;
    suffix.clear();
}


void solve() {
    cin >> s;
    int n = strlen(s);
    build();


    clear();
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case " << i << ": " ;
        solve();
    }
}