后缀自动机代码模板

 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

const int N = 100010, M = N * 2;

int n;
char str[N];
struct SAM {
    int maxlen[M], trans[M][26], link[M], sz, last;
    SAM() { sz = last = 1; }
    void init() {
        memset(maxlen, 0, sizeof maxlen);
        memset(trans, 0, sizeof trans);
        memset(link, 0, sizeof link);
        sz = last = 1;
    }
    void extend(int ch) {
        int cur = ++sz, p = last;
        maxlen[cur] = maxlen[p] + 1;
        cnt[cur] = 1;
        for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
        if(!p) link[cur] = 1;
        else {
            int q = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
            else {
                int clone = ++sz;
                maxlen[clone] = maxlen[p] + 1;
                memcpy(trans[clone], trans[q], sizeof trans[clone]);
                link[clone] = link[q];
                for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
                link[cur] = link[q] = clone;
            }
        }
        last = cur;
    }
} sam;

for (int i = 0; str[i]; i++) sam.extend(str[i] - 'a');
for(int i = 1; i <= sam.sz; i++) a[sam.maxlen[i]]++;
for(int i = 1; i <= sam.sz; i++) a[i] += a[i - 1];
for(int i = 1; i <= sam.sz; i++) b[a[sam.maxlen[i]]--] = i;