LCPArray
(String/LCPArray.hpp)

• View this file on GitHub
• Last update: 2023-07-19 16:58:05+00:00
• Include: #include "String/LCPArray.hpp"

LCPArray

vector<int> LCPArray(string S, vector<int> sa)

$S$ の長さを $N$ として, 長さ $N$ の配列を返す. $i$番目の要素はsa[i]とsa[i+1]の最長共通接頭辞．

制約

• sa は $S$ のSuffixArray(空文字を含む)．

計算量

• $O(N)$

Verified with

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

Code

vector<int> LCPArray(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n + 1);
    for (int i = 0; i <= n; i++) {
        rank[sa[i]] = i;
    }
    vector<int> lcp(n, 0);
    int h = 0;
    for (int i = 0; i < n; i++) {
        int j = sa[rank[i] - 1];
        if (h > 0) h--;
        for (; j + h < n && i + h < n; h++) {
            if (s[j + h] != s[i + h]) break;
        }
        lcp[rank[i] - 1] = h;
    }
    return lcp;
}

#line 1 "String/LCPArray.hpp"
vector<int> LCPArray(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n + 1);
    for (int i = 0; i <= n; i++) {
        rank[sa[i]] = i;
    }
    vector<int> lcp(n, 0);
    int h = 0;
    for (int i = 0; i < n; i++) {
        int j = sa[rank[i] - 1];
        if (h > 0) h--;
        for (; j + h < n && i + h < n; h++) {
            if (s[j + h] != s[i + h]) break;
        }
        lcp[rank[i] - 1] = h;
    }
    return lcp;
}

Back to top page