Longest Common Prefix Array
(string/lcp_array.hpp)

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Include: #include "string/lcp_array.hpp"

Description

高さ配列 (LCP array) は，接尾辞配列における隣同士の接尾辞で，先頭何文字が共通しているかを表す配列である．lcp[i] は接尾辞 s[sa[i]..] と接尾辞 s[sa[i + 1]..] の先頭で共通している文字数になる．

Operations

• vector<int> lcp_array(string s, SuffixArray sa)
  • 文字列 s と s の接尾辞配列 sa から高さ配列を構築する
  • 時間計算量: $O(n)$

Required by

• Longest Common Substring (string/longest_common_substring.hpp)

Verified with

• test/yosupo/longest_common_substring.test.cpp
• test/yosupo/number_of_substrings.test.cpp

Code

#pragma once
#include <string>
#include <vector>

template <typename T>
std::vector<int> lcp_array(const std::vector<T>& s,
                           const std::vector<int>& sa) {
    const int n = s.size();
    std::vector<int> rank(n);
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    int h = 0;
    std::vector<int> lcp(n - 1);
    for (int i = 0; i < n; ++i) {
        if (h > 0) --h;
        if (rank[i] == 0) continue;
        int j = sa[rank[i] - 1];
        while (j + h < n && i + h < n && s[j + h] == s[i + h]) ++h;
        lcp[rank[i] - 1] = h;
    }
    return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
    return lcp_array(std::vector<char>(s.begin(), s.end()), sa);
}

#line 2 "string/lcp_array.hpp"
#include <string>
#include <vector>

template <typename T>
std::vector<int> lcp_array(const std::vector<T>& s,
                           const std::vector<int>& sa) {
    const int n = s.size();
    std::vector<int> rank(n);
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    int h = 0;
    std::vector<int> lcp(n - 1);
    for (int i = 0; i < n; ++i) {
        if (h > 0) --h;
        if (rank[i] == 0) continue;
        int j = sa[rank[i] - 1];
        while (j + h < n && i + h < n && s[j + h] == s[i + h]) ++h;
        lcp[rank[i] - 1] = h;
    }
    return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
    return lcp_array(std::vector<char>(s.begin(), s.end()), sa);
}

Back to top page