Code-Library/Suffix array construction.cpp at master · shahed-shd/Code-Library · 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
// Suffix array construction
// Time Complexity : O(n*log(n)*log(n))


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;


struct suff {
    int idx;
    int rnk[2];
};


bool suff_cmp(const suff &a, const suff &b)
{
    if(a.rnk[0] == b.rnk[0])
        return a.rnk[1] < b.rnk[1];

    return a.rnk[0] < b.rnk[0];
}


void build_suff_arr(char str[], int len, int suff_arr[])
{
    suff suffixes[len];

    for(int i = 0; i < len; ++i) {
        suff &sf = suffixes[i];
        sf.idx = i;
        sf.rnk[0] = str[i];
        sf.rnk[1] = (i+1 < len)? str[i+1] : -1;
    }

    sort(suffixes, suffixes+len, suff_cmp);
    int idx_rnk[len];

    for(int k = 4; k < 2*len; k *= 2) {
        int prev_suff_rnk0 = -1;
        int prev_suff_rnk1 = -1;
        int rnk = -1;

        for(int i = 0; i < len; ++i) {
            suff &sf = suffixes[i];

            if(sf.rnk[0] == prev_suff_rnk0 and sf.rnk[1] == prev_suff_rnk1) {
                sf.rnk[0] = rnk;
            }
            else {
                prev_suff_rnk0 = sf.rnk[0];
                prev_suff_rnk1 = sf.rnk[1];
                sf.rnk[0] = ++rnk;
            }

            idx_rnk[sf.idx] = rnk;
        }

        for(int i = 0; i < len; ++i) {
            int next_idx = suffixes[i].idx + k/2;
            suffixes[i].rnk[1] = (next_idx < len)? idx_rnk[next_idx] : -1;
        }

        sort(suffixes, suffixes+len, suff_cmp);
    }

    for(int i = 0; i < len; ++i)
        suff_arr[i] = suffixes[i].idx;
}


int main()
{
    char str[100] = "banana";

    int len = strlen(str);
    int suff_arr[100];

    build_suff_arr(str, len, suff_arr);

    puts("Suffix array:");

    for(int i = 0; i < len; ++i)
        printf("%d ", suff_arr[i]);

    puts("\n\nSorted suffixes:");

    for(int i = 0; i < len; ++i)
        puts(str + suff_arr[i]);

    return 0;
}

/*
Output:

Suffix array:
5 3 1 0 4 2

Sorted suffixes:
a
ana
anana
banana
na
nana

*/