SuffixArray
(String/SuffixArray.hpp)

• View this file on GitHub
• Last update: 2023-07-19 13:59:31+00:00
• Include: #include "String/SuffixArray.hpp"

SuffixArray

vector<int> SuffixArray(string S)

$S$ について(空文字を含む)SuffixArrayを返す. $S$ の長さを $N$ として、長さ $ N+1 $ の配列を返す.

計算量

• $ O( N \log N ) $

SuffixArray とは？

接尾辞(先頭から $ n \in {0, \ldots, N } $ 文字を取り除いた文字列)を，辞書順に並べたもの．

たとえばsuffixarrayについて，

$n$	接尾辞
0	suffixarray
1	uffixarray
2	ffixarray
3	fixarray
4	ixarray
5	xarray
6	array
7	rray
8	ray
9	ay
10	y
11	` `

である．これを接尾辞について辞書順に並び変えると，

$n$	接尾辞
11	` `
6	array
9	ay
2	ffixarray
3	fixarray
4	ixarray
8	ray
7	rray
0	suffixarray
1	uffixarray
5	xarray
10	y

となるので，suffixarrayのSuffixArrayは{11, 6, 9, 2, 3, 4, 8, 7, 0, 1, 5, 10}である．よってこれが返る．

Verified with

• Test/yosupo-Number-of-Substrings.test.cpp
• Test/yosupo-Suffix-Array.test.cpp

Code

vector<int> SuffixArray(const string& s) {
    int n = s.size(), k;
    vector<int> sa(n + 1);
    vector<int> rank(n + 1);
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rank[i] = i < n ? (int)s[i] : -1;
    }

    auto compare = [&](int a, int b) {
        if (rank[a] != rank[b]) return rank[a] < rank[b];
        auto rank_ak = a + k <= n ? rank[a + k] : -1;
        auto rank_bk = b + k <= n ? rank[b + k] : -1;
        return rank_ak < rank_bk;
    };

    for (k = 1; k <= n; k *= 2) {
        sort(sa.begin(), sa.end(), compare);
        vector<int> tmp(n + 1);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            rank[i] = tmp[i];
        }
    }
    return sa;
}

#line 1 "String/SuffixArray.hpp"
vector<int> SuffixArray(const string& s) {
    int n = s.size(), k;
    vector<int> sa(n + 1);
    vector<int> rank(n + 1);
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rank[i] = i < n ? (int)s[i] : -1;
    }

    auto compare = [&](int a, int b) {
        if (rank[a] != rank[b]) return rank[a] < rank[b];
        auto rank_ak = a + k <= n ? rank[a + k] : -1;
        auto rank_bk = b + k <= n ? rank[b + k] : -1;
        return rank_ak < rank_bk;
    };

    for (k = 1; k <= n; k *= 2) {
        sort(sa.begin(), sa.end(), compare);
        vector<int> tmp(n + 1);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            rank[i] = tmp[i];
        }
    }
    return sa;
}

Back to top page