Longest Common Extension
(string/longest_common_extension.hpp)

• View this file on GitHub
• Last update: 2026-07-09 02:40:33+09:00
• Include: #include "string/longest_common_extension.hpp"

Overview

LongestCommonExtension is a static structure for longest-common-extension queries on one sequence. It returns the longest common prefix length of suffixes starting at two positions, which is useful for substring comparison, runs, repetitions, and suffix-array based string problems.

The implementation builds a suffix array, the adjacent LCP array, and a sparse table over the LCP array. Queries are deterministic and do not use hashing.

Sequence must provide size(), operator[], begin(), and end(). Elements must be sortable for construction. The comparison helpers also require element <.

Methods

Let N = size().

Method	Description	Complexity
LongestCommonExtension()	Creates an empty structure.	O(1)
LongestCommonExtension(const Sequence& sequence)	Copies sequence and builds the structure.	O(N \log N)
LongestCommonExtension(Sequence&& sequence)	Moves sequence and builds the structure.	O(N \log N)
int size() const	Returns N.	O(1)
bool empty() const	Returns whether N == 0.	O(1)
const Sequence& sequence() const	Returns the stored sequence.	O(1)
const vector<int>& suffix_array() const	Returns suffix starts in lexicographic order.	O(1)
const vector<int>& rank() const	Returns inverse suffix-array ranks.	O(1)
const vector<int>& lcp_array() const	Returns adjacent suffix LCP lengths.	O(1)
int longest_common_extension(int i, int j) const	Returns LCP(sequence[i..], sequence[j..]).	O(1)
int longest_common_extension(int i, int j, int limit) const	Returns min(longest_common_extension(i, j), limit).	O(1)
int lcp(int i, int j) const	Alias of longest_common_extension(i, j).	O(1)
int operator()(int i, int j) const	Alias of longest_common_extension(i, j).	O(1)
int compare_suffix(int i, int j) const	Lexicographically compares suffixes.	O(1)
int compare(int l1, int r1, int l2, int r2) const	Lexicographically compares two half-open substrings.	O(1)

longest_common_extension(i, i) returns N - i. Positions i and j may be N, representing the empty suffix. Other indices must be in [0, N].

compare_suffix and compare return -1, 0, or 1.

The memory usage is O(N \log N).

Example

#include "string/longest_common_extension.hpp"

#include <iostream>
#include <string>

int main() {
    std::string text = "banana";
    m1une::string::LongestCommonExtension<> extension(text);

    std::cout << extension.longest_common_extension(1, 3) << "\n"; // 3
    std::cout << extension.compare(1, 4, 3, 6) << "\n";            // 0
}

Depends on

• Suffix Array and LCP Array (string/suffix_array.hpp)

Required by

• String Algorithms Bundle (string/all.hpp)

Verified with

• verify/string/longest_common_extension.test.cpp
• verify/string/string_algorithms.test.cpp

Code

#ifndef M1UNE_STRING_LONGEST_COMMON_EXTENSION_HPP
#define M1UNE_STRING_LONGEST_COMMON_EXTENSION_HPP 1

#include <algorithm>
#include <cassert>
#include <string>
#include <utility>
#include <vector>

#include "suffix_array.hpp"

namespace m1une {
namespace string {

template <class Sequence = std::string>
struct LongestCommonExtension {
   private:
    Sequence _sequence;
    std::vector<int> _suffix_array;
    std::vector<int> _rank;
    std::vector<int> _lcp;
    std::vector<int> _log;
    std::vector<std::vector<int>> _table;

    int range_min(int left, int right) const {
        assert(0 <= left && left < right && right <= int(_lcp.size()));
        int k = _log[right - left];
        return std::min(_table[k][left], _table[k][right - (1 << k)]);
    }

    void build() {
        int n = int(_sequence.size());
        _suffix_array = m1une::string::suffix_array(_sequence);
        _rank.assign(n, 0);
        for (int i = 0; i < n; i++) {
            _rank[_suffix_array[i]] = i;
        }

        _lcp = m1une::string::lcp_array(_sequence, _suffix_array);
        int m = int(_lcp.size());
        _log.assign(m + 1, 0);
        for (int i = 2; i <= m; i++) {
            _log[i] = _log[i >> 1] + 1;
        }

        _table.clear();
        if (m == 0) return;
        _table.assign(_log[m] + 1, std::vector<int>());
        _table[0] = _lcp;
        for (int k = 1; k < int(_table.size()); k++) {
            int width = 1 << k;
            int half = width >> 1;
            _table[k].resize(m - width + 1);
            for (int i = 0; i + width <= m; i++) {
                _table[k][i] = std::min(_table[k - 1][i], _table[k - 1][i + half]);
            }
        }
    }

   public:
    LongestCommonExtension() = default;

    explicit LongestCommonExtension(const Sequence& sequence) : _sequence(sequence) {
        build();
    }

    explicit LongestCommonExtension(Sequence&& sequence) : _sequence(std::move(sequence)) {
        build();
    }

    int size() const {
        return int(_sequence.size());
    }

    bool empty() const {
        return _sequence.empty();
    }

    const Sequence& sequence() const {
        return _sequence;
    }

    const std::vector<int>& suffix_array() const {
        return _suffix_array;
    }

    const std::vector<int>& rank() const {
        return _rank;
    }

    const std::vector<int>& lcp_array() const {
        return _lcp;
    }

    int longest_common_extension(int i, int j) const {
        int n = size();
        assert(0 <= i && i <= n);
        assert(0 <= j && j <= n);
        if (i == j) return n - i;
        if (i == n || j == n) return 0;

        int left = _rank[i];
        int right = _rank[j];
        if (left > right) std::swap(left, right);
        return range_min(left, right);
    }

    int longest_common_extension(int i, int j, int limit) const {
        assert(0 <= limit);
        return std::min(longest_common_extension(i, j), limit);
    }

    int lcp(int i, int j) const {
        return longest_common_extension(i, j);
    }

    int operator()(int i, int j) const {
        return longest_common_extension(i, j);
    }

    int compare_suffix(int i, int j) const {
        int n = size();
        assert(0 <= i && i <= n);
        assert(0 <= j && j <= n);
        if (i == j) return 0;
        int common = longest_common_extension(i, j);
        if (i + common == n && j + common == n) return 0;
        if (i + common == n) return -1;
        if (j + common == n) return 1;
        return _sequence[i + common] < _sequence[j + common] ? -1 : 1;
    }

    int compare(int l1, int r1, int l2, int r2) const {
        int n = size();
        assert(0 <= l1 && l1 <= r1 && r1 <= n);
        assert(0 <= l2 && l2 <= r2 && r2 <= n);
        int len1 = r1 - l1;
        int len2 = r2 - l2;
        int common = longest_common_extension(l1, l2, std::min(len1, len2));
        if (common == len1 && common == len2) return 0;
        if (common == len1) return -1;
        if (common == len2) return 1;
        return _sequence[l1 + common] < _sequence[l2 + common] ? -1 : 1;
    }
};

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_LONGEST_COMMON_EXTENSION_HPP

#line 1 "string/longest_common_extension.hpp"



#include <algorithm>
#include <cassert>
#include <string>
#include <utility>
#include <vector>

#line 1 "string/suffix_array.hpp"



#line 6 "string/suffix_array.hpp"
#include <numeric>
#line 8 "string/suffix_array.hpp"
#include <type_traits>
#line 10 "string/suffix_array.hpp"

namespace m1une {
namespace string {
namespace detail {

template <class Sequence>
std::vector<int> suffix_array_impl(const Sequence& sequence) {
    int n = int(sequence.size());
    if (n == 0) return {};

    using Value = std::remove_cv_t<std::remove_reference_t<decltype(sequence[0])>>;
    std::vector<Value> sorted(sequence.begin(), sequence.end());
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());

    int length = n + 1;
    std::vector<int> order(length);
    std::vector<int> rank(length);
    std::vector<int> key(length);
    key[n] = 0;
    for (int i = 0; i < n; i++) {
        key[i] = int(std::lower_bound(sorted.begin(), sorted.end(), sequence[i]) - sorted.begin()) + 1;
    }

    int alphabet = int(sorted.size()) + 1;
    std::vector<int> count(std::max(length, alphabet), 0);
    for (int value : key) count[value]++;
    for (int i = 1; i < alphabet; i++) count[i] += count[i - 1];
    for (int i = length - 1; i >= 0; i--) order[--count[key[i]]] = i;

    int classes = 1;
    rank[order[0]] = 0;
    for (int i = 1; i < length; i++) {
        if (key[order[i - 1]] != key[order[i]]) classes++;
        rank[order[i]] = classes - 1;
    }

    std::vector<int> shifted(length);
    std::vector<int> next_rank(length);
    for (long long half = 1; half < length; half <<= 1) {
        for (int i = 0; i < length; i++) {
            long long position = order[i] - half;
            if (position < 0) position += length;
            shifted[i] = int(position);
        }

        count.assign(classes, 0);
        for (int position : shifted) count[rank[position]]++;
        for (int i = 1; i < classes; i++) count[i] += count[i - 1];
        for (int i = length - 1; i >= 0; i--) {
            int position = shifted[i];
            order[--count[rank[position]]] = position;
        }

        int next_classes = 1;
        next_rank[order[0]] = 0;
        for (int i = 1; i < length; i++) {
            int current = order[i];
            int previous = order[i - 1];
            int current_second = int((current + half) % length);
            int previous_second = int((previous + half) % length);
            if (
                rank[current] != rank[previous] ||
                rank[current_second] != rank[previous_second]
            ) {
                next_classes++;
            }
            next_rank[current] = next_classes - 1;
        }
        rank.swap(next_rank);
        classes = next_classes;
        if (classes == length) break;
    }

    std::vector<int> suffixes(n);
    for (int i = 0; i < n; i++) suffixes[i] = order[i + 1];
    return suffixes;
}

}  // namespace detail

template <class Sequence>
std::vector<int> suffix_array(const Sequence& sequence) {
    return detail::suffix_array_impl(sequence);
}

inline std::vector<int> suffix_array(const std::string& text) {
    std::vector<unsigned char> values;
    values.reserve(text.size());
    for (unsigned char character : text) values.push_back(character);
    return detail::suffix_array_impl(values);
}

template <class Sequence>
std::vector<int> lcp_array(const Sequence& sequence, const std::vector<int>& suffixes) {
    int n = int(sequence.size());
    assert(int(suffixes.size()) == n);
    if (n == 0) return {};

    std::vector<int> rank(n);
    for (int i = 0; i < n; i++) {
        assert(0 <= suffixes[i] && suffixes[i] < n);
        rank[suffixes[i]] = i;
    }

    std::vector<int> lcp(n - 1);
    int common = 0;
    for (int i = 0; i < n; i++) {
        int position = rank[i];
        if (position == n - 1) {
            common = 0;
            continue;
        }
        int j = suffixes[position + 1];
        while (
            i + common < n &&
            j + common < n &&
            sequence[i + common] == sequence[j + common]
        ) {
            common++;
        }
        lcp[position] = common;
        if (common > 0) common--;
    }
    return lcp;
}

}  // namespace string
}  // namespace m1une


#line 11 "string/longest_common_extension.hpp"

namespace m1une {
namespace string {

template <class Sequence = std::string>
struct LongestCommonExtension {
   private:
    Sequence _sequence;
    std::vector<int> _suffix_array;
    std::vector<int> _rank;
    std::vector<int> _lcp;
    std::vector<int> _log;
    std::vector<std::vector<int>> _table;

    int range_min(int left, int right) const {
        assert(0 <= left && left < right && right <= int(_lcp.size()));
        int k = _log[right - left];
        return std::min(_table[k][left], _table[k][right - (1 << k)]);
    }

    void build() {
        int n = int(_sequence.size());
        _suffix_array = m1une::string::suffix_array(_sequence);
        _rank.assign(n, 0);
        for (int i = 0; i < n; i++) {
            _rank[_suffix_array[i]] = i;
        }

        _lcp = m1une::string::lcp_array(_sequence, _suffix_array);
        int m = int(_lcp.size());
        _log.assign(m + 1, 0);
        for (int i = 2; i <= m; i++) {
            _log[i] = _log[i >> 1] + 1;
        }

        _table.clear();
        if (m == 0) return;
        _table.assign(_log[m] + 1, std::vector<int>());
        _table[0] = _lcp;
        for (int k = 1; k < int(_table.size()); k++) {
            int width = 1 << k;
            int half = width >> 1;
            _table[k].resize(m - width + 1);
            for (int i = 0; i + width <= m; i++) {
                _table[k][i] = std::min(_table[k - 1][i], _table[k - 1][i + half]);
            }
        }
    }

   public:
    LongestCommonExtension() = default;

    explicit LongestCommonExtension(const Sequence& sequence) : _sequence(sequence) {
        build();
    }

    explicit LongestCommonExtension(Sequence&& sequence) : _sequence(std::move(sequence)) {
        build();
    }

    int size() const {
        return int(_sequence.size());
    }

    bool empty() const {
        return _sequence.empty();
    }

    const Sequence& sequence() const {
        return _sequence;
    }

    const std::vector<int>& suffix_array() const {
        return _suffix_array;
    }

    const std::vector<int>& rank() const {
        return _rank;
    }

    const std::vector<int>& lcp_array() const {
        return _lcp;
    }

    int longest_common_extension(int i, int j) const {
        int n = size();
        assert(0 <= i && i <= n);
        assert(0 <= j && j <= n);
        if (i == j) return n - i;
        if (i == n || j == n) return 0;

        int left = _rank[i];
        int right = _rank[j];
        if (left > right) std::swap(left, right);
        return range_min(left, right);
    }

    int longest_common_extension(int i, int j, int limit) const {
        assert(0 <= limit);
        return std::min(longest_common_extension(i, j), limit);
    }

    int lcp(int i, int j) const {
        return longest_common_extension(i, j);
    }

    int operator()(int i, int j) const {
        return longest_common_extension(i, j);
    }

    int compare_suffix(int i, int j) const {
        int n = size();
        assert(0 <= i && i <= n);
        assert(0 <= j && j <= n);
        if (i == j) return 0;
        int common = longest_common_extension(i, j);
        if (i + common == n && j + common == n) return 0;
        if (i + common == n) return -1;
        if (j + common == n) return 1;
        return _sequence[i + common] < _sequence[j + common] ? -1 : 1;
    }

    int compare(int l1, int r1, int l2, int r2) const {
        int n = size();
        assert(0 <= l1 && l1 <= r1 && r1 <= n);
        assert(0 <= l2 && l2 <= r2 && r2 <= n);
        int len1 = r1 - l1;
        int len2 = r2 - l2;
        int common = longest_common_extension(l1, l2, std::min(len1, len2));
        if (common == len1 && common == len2) return 0;
        if (common == len1) return -1;
        if (common == len2) return 1;
        return _sequence[l1 + common] < _sequence[l2 + common] ? -1 : 1;
    }
};

}  // namespace string
}  // namespace m1une

Back to top page