Algorithm-DataStructure/SuffixArray-O(nlogn).cpp at master · QuqqU/Algorithm-DataStructure · 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
123
124
125
126
127
128
//sa, lcp 0-based
//g, tg - 1-based
void f() {
    int n = s.size();
    if(n == 1) return;

    int lim = max(26, n);
    for(int i = 0; i < n; i++) sa[i] = i, g[i] = s[i] - 'a' + 1;

    for(int t = 1; t < n ; t <<= 1) {
        for(int i = 0; i <= lim; i++) cnt[i] = 0;
        for(int i = 0; i < n; i++) cnt[g[min(i + t, n)]]++;
        for(int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
        for(int i = n - 1; i >=0; i--) tg[--cnt[g[min(i + t, n)]]] = i;
        for(int i = 0; i <= lim; i++) cnt[i] = 0;
        for(int i = 0; i < n; i++) cnt[g[i]]++;
        for(int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
        for(int i = n - 1; i >=0; i--) sa[--cnt[g[tg[i]]]] = tg[i];

        auto cmp = [&](int i, int j) {
            if(g[i] == g[j]) return g[i + t] < g[j + t];
            return g[i] < g[j];
        };

        tg[sa[0]] = 1;
        for(int i = 1; i < n; i++) tg[sa[i]] = tg[sa[i - 1]] + cmp(sa[i - 1], sa[i]);

        swap(g, tg);

        if(g[n] == n) break;
    }
}

//////////////////////////////////

const int MAX = 500'005;


int sa[MAX], lcp[MAX], g[MAX], gg[MAX], tg[MAX], cnt[MAX];


void f(const string& s) {
    int n = s.size();
    if(n == 1) return;

    int lim = max(26, n);
    for(int i = 0; i < n; i++) sa[i] = i, g[i] = s[i] - 'a' + 1;


    for(int t = 1; t < n; t <<= 1) {
        for(int i = 0; i <= lim; i++) cnt[i] = 0;
        for(int i = 0; i < n; i++) cnt[g[min(i + t, n)]]++;
        for(int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
        for(int i = n - 1; i >= 0; i--) gg[--cnt[g[min(i + t, n)]]] = i;

        for(int i = 0; i <= lim; i++) cnt[i] = 0;
        for(int i = 0; i < n; i++) cnt[g[i]]++;
        for(int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
        for(int i = n - 1; i >= 0; i--) sa[--cnt[g[gg[i]]]] = gg[i];


        auto cmp = [&](int i, int j) {
            if(g[i] == g[j]) return g[i + t] < g[j + t];
            return g[i] < g[j];
        };

        tg[sa[0]] = 1;
        for(int i = 1; i < n; i++) tg[sa[i]] = tg[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
        for(int i = 0; i < n; i++) g[i] = tg[i];
    }


    for(int i = 0, k = 0; i < n; i++, k = max(k - 1, 0)) {
        if(g[i] - 1 == n - 1) continue;
        int j = sa[(g[i] - 1) + 1];
        while(s[i + k] == s[j + k]) k++;

        lcp[g[i] - 1] = k;
    }


}


///////////////////////////////////////////////////


void f(const string& s) {
    int n = s.size();
    if(n == 1) return;

    int lim = max(26, n);
    for(int i = 0; i < n; i++) sa[i] = i, g[i] = s[i] - 'a' + 1;

    for(int t = 1; t < n; t <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; i++) cnt[g[min(i + t, n)]]++;
        for(int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
        for(int i = n - 1; i >= 0; i--) gg[--cnt[g[min(i + t, n)]]] = i;

        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; i++) cnt[g[i]]++;
        for(int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
        for(int i = n - 1; i >= 0; i--) sa[--cnt[g[gg[i]]]] = gg[i];

        auto cmp = [&](int i, int j) {
            if(g[i] == g[j]) return g[i + t] < g[j + t];
            return g[i] < g[j];
        };

        tg[sa[0]] = 1;
        for(int i = 1; i < n; i++) tg[sa[i]] = tg[sa[i - 1]] + cmp(sa[i - 1], sa[i]);

        memcpy(g, tg, sizeof(g));
    }

    for(int i = 0, k = 0; i < n; i++, k = max(k - 1, 0)) {
        if(g[i] - 1 == n - 1) continue;
        int j = sa[(g[i] - 1) + 1];
        while(s[i + k] == s[j + k]) k++;

        lcp[g[i] - 1] = k;
    }
}