最長共通接頭辞 (lib/string/lcp.hpp)

• View this file on GitHub
• Last update: 2025-05-22 02:35:49+09:00
• Include: #include "lib/string/lcp.hpp"

Code

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

/// @brief 最長共通接頭辞
template <class T>
int longest_common_prefix(const std::vector<T> &a, const std::vector<T> &b) {
    int m = (int)std::min(a.size(), b.size());
    for (int i = 0; i < m; ++i) {
        if (a[i] != b[i]) return i;
    }
    return m;
}

/// @brief 最長共通接頭辞
int longest_common_prefix(const std::string &a, const std::string &b) {
    int m = (int)std::min(a.size(), b.size());
    for (int i = 0; i < m; ++i) {
        if (a[i] != b[i]) return i;
    }
    return m;
}

#line 2 "lib/string/lcp.hpp"
#include <algorithm>
#include <string>
#include <vector>

/// @brief 最長共通接頭辞
template <class T>
int longest_common_prefix(const std::vector<T> &a, const std::vector<T> &b) {
    int m = (int)std::min(a.size(), b.size());
    for (int i = 0; i < m; ++i) {
        if (a[i] != b[i]) return i;
    }
    return m;
}

/// @brief 最長共通接頭辞
int longest_common_prefix(const std::string &a, const std::string &b) {
    int m = (int)std::min(a.size(), b.size());
    for (int i = 0; i < m; ++i) {
        if (a[i] != b[i]) return i;
    }
    return m;
}

Back to top page