LCP Array
(lib/string/lcp_array.hpp)

• View this file on GitHub
• Last update: 2024-10-31 22:40:32+09:00
• Include: #include "lib/string/lcp_array.hpp"

LCP Array

概要

文字列 $S$ について、LCP 配列を求めます。

計算量

$\mathrm{O}(\lvert S\lvert)$

Verified with

• test/library_checker/string/number_of_substrings_1.test.cpp

Code

#pragma once

/**
 * @brief LCP Array
 * @docs docs/string/lcp_array.md
 */

#include <vector>

// Kasai's Algorithm
template <typename T>
std::vector<int> LCPArray(const 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;
    }

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

#line 2 "lib/string/lcp_array.hpp"

/**
 * @brief LCP Array
 * @docs docs/string/lcp_array.md
 */

#include <vector>

// Kasai's Algorithm
template <typename T>
std::vector<int> LCPArray(const 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;
    }

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

Back to top page