Longest Common Substring
(string/longest_common_substring.hpp)

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

Overview

longest_common_substring(first, second) finds one longest sequence that occurs as a contiguous substring of both inputs. It returns the matching half-open interval in each input.

The implementation builds a suffix array and adjacent LCP array over the two inputs joined by a unique separator. Input symbols are coordinate-compressed, so the separator cannot collide with a real symbol.

Sequence must provide size(), operator[], begin(), and end(). Elements must be sortable and equality-comparable.

Result

Field or Method	Description	Complexity
int first_left, int first_right	Half-open interval in the first sequence.	O(1)
int second_left, int second_right	Half-open interval in the second sequence.	O(1)
int length() const	Returns the common substring length.	O(1)
bool empty() const	Returns whether the length is zero.	O(1)
pair<int, int> first_interval() const	Returns {first_left, first_right}.	O(1)
pair<int, int> second_interval() const	Returns {second_left, second_right}.	O(1)

If there is no common nonempty substring, all endpoints are zero. When several maximum substrings exist, any one of them may be returned.

Function

Function	Description	Complexity
LongestCommonSubstring longest_common_substring(const Sequence& first, const Sequence& second)	Finds one longest common substring.	O((N + M) \log(N + M))

The memory usage is O(N + M).

Example

#include "string/longest_common_substring.hpp"

#include <iostream>
#include <string>

int main() {
    std::string first = "xabxac";
    std::string second = "abcabxabcd";
    auto result = m1une::string::longest_common_substring(first, second);

    std::cout << result.first_left << " " << result.first_right << "\n";
    std::cout << result.second_left << " " << result.second_right << "\n";
}

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_substring.test.cpp
• verify/string/string_algorithms.test.cpp

Code

#ifndef M1UNE_STRING_LONGEST_COMMON_SUBSTRING_HPP
#define M1UNE_STRING_LONGEST_COMMON_SUBSTRING_HPP 1

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

#include "suffix_array.hpp"

namespace m1une {
namespace string {

struct LongestCommonSubstring {
    int first_left = 0;
    int first_right = 0;
    int second_left = 0;
    int second_right = 0;

    int length() const {
        assert(first_right - first_left == second_right - second_left);
        return first_right - first_left;
    }

    bool empty() const {
        return length() == 0;
    }

    std::pair<int, int> first_interval() const {
        return {first_left, first_right};
    }

    std::pair<int, int> second_interval() const {
        return {second_left, second_right};
    }
};

namespace detail {

template <class Sequence>
std::vector<int> compressed_join_with_separator(const Sequence& first, const Sequence& second) {
    using Value = std::remove_cv_t<std::remove_reference_t<decltype(first[0])>>;

    std::vector<Value> values;
    values.reserve(first.size() + second.size());
    for (const auto& value : first) values.push_back(value);
    for (const auto& value : second) values.push_back(value);
    std::sort(values.begin(), values.end());
    values.erase(std::unique(values.begin(), values.end()), values.end());

    std::vector<int> joined;
    joined.reserve(first.size() + second.size() + 1);
    for (const auto& value : first) {
        joined.push_back(int(std::lower_bound(values.begin(), values.end(), value) - values.begin()) + 2);
    }
    joined.push_back(1);
    for (const auto& value : second) {
        joined.push_back(int(std::lower_bound(values.begin(), values.end(), value) - values.begin()) + 2);
    }
    return joined;
}

}  // namespace detail

template <class Sequence>
LongestCommonSubstring longest_common_substring(const Sequence& first, const Sequence& second) {
    int n = int(first.size());
    int m = int(second.size());
    std::vector<int> joined = detail::compressed_join_with_separator(first, second);
    std::vector<int> suffixes = suffix_array(joined);
    std::vector<int> lcp = lcp_array(joined, suffixes);

    LongestCommonSubstring result;
    for (int i = 0; i + 1 < int(suffixes.size()); i++) {
        int a = suffixes[i];
        int b = suffixes[i + 1];
        if (a == n || b == n) continue;

        bool a_first = a < n;
        bool b_first = b < n;
        if (a_first == b_first) continue;

        int first_left = a_first ? a : b;
        int second_left = a_first ? b - n - 1 : a - n - 1;
        int length = lcp[i];
        length = std::min(length, n - first_left);
        length = std::min(length, m - second_left);
        if (length > result.length()) {
            result.first_left = first_left;
            result.first_right = first_left + length;
            result.second_left = second_left;
            result.second_right = second_left + length;
        }
    }
    return result;
}

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_LONGEST_COMMON_SUBSTRING_HPP

#line 1 "string/longest_common_substring.hpp"



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

#line 1 "string/suffix_array.hpp"



#line 6 "string/suffix_array.hpp"
#include <numeric>
#include <string>
#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_substring.hpp"

namespace m1une {
namespace string {

struct LongestCommonSubstring {
    int first_left = 0;
    int first_right = 0;
    int second_left = 0;
    int second_right = 0;

    int length() const {
        assert(first_right - first_left == second_right - second_left);
        return first_right - first_left;
    }

    bool empty() const {
        return length() == 0;
    }

    std::pair<int, int> first_interval() const {
        return {first_left, first_right};
    }

    std::pair<int, int> second_interval() const {
        return {second_left, second_right};
    }
};

namespace detail {

template <class Sequence>
std::vector<int> compressed_join_with_separator(const Sequence& first, const Sequence& second) {
    using Value = std::remove_cv_t<std::remove_reference_t<decltype(first[0])>>;

    std::vector<Value> values;
    values.reserve(first.size() + second.size());
    for (const auto& value : first) values.push_back(value);
    for (const auto& value : second) values.push_back(value);
    std::sort(values.begin(), values.end());
    values.erase(std::unique(values.begin(), values.end()), values.end());

    std::vector<int> joined;
    joined.reserve(first.size() + second.size() + 1);
    for (const auto& value : first) {
        joined.push_back(int(std::lower_bound(values.begin(), values.end(), value) - values.begin()) + 2);
    }
    joined.push_back(1);
    for (const auto& value : second) {
        joined.push_back(int(std::lower_bound(values.begin(), values.end(), value) - values.begin()) + 2);
    }
    return joined;
}

}  // namespace detail

template <class Sequence>
LongestCommonSubstring longest_common_substring(const Sequence& first, const Sequence& second) {
    int n = int(first.size());
    int m = int(second.size());
    std::vector<int> joined = detail::compressed_join_with_separator(first, second);
    std::vector<int> suffixes = suffix_array(joined);
    std::vector<int> lcp = lcp_array(joined, suffixes);

    LongestCommonSubstring result;
    for (int i = 0; i + 1 < int(suffixes.size()); i++) {
        int a = suffixes[i];
        int b = suffixes[i + 1];
        if (a == n || b == n) continue;

        bool a_first = a < n;
        bool b_first = b < n;
        if (a_first == b_first) continue;

        int first_left = a_first ? a : b;
        int second_left = a_first ? b - n - 1 : a - n - 1;
        int length = lcp[i];
        length = std::min(length, n - first_left);
        length = std::min(length, m - second_left);
        if (length > result.length()) {
            result.first_left = first_left;
            result.first_right = first_left + length;
            result.second_left = second_left;
            result.second_right = second_left + length;
        }
    }
    return result;
}

}  // namespace string
}  // namespace m1une

Back to top page