1//! @file match.hpp
2//! @author ryftchen
3//! @brief The declarations (match) in the algorithm module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <cstdint>
10
11//! @brief The algorithm module.
12namespace algorithm // NOLINT(modernize-concat-nested-namespaces)
13{
14//! @brief Match-related functions in the algorithm module.
15namespace match
16{
17//! @brief Brief function description.
18//! @return function description (module_function)
19inline static const char* description() noexcept
20{
21 return "ALGO_MATCH";
22}
23extern const char* version() noexcept;
24
25//! @brief Match methods.
26class Match
27{
28public:
29 //! @brief Rabin-Karp.
30 //! @param text - matching text
31 //! @param pattern - single pattern
32 //! @param textLen - length of matching text
33 //! @param patternLen - length of single pattern
34 //! @return index in matching text
35 static std::int64_t rk(
36 const unsigned char* const text,
37 const unsigned char* const pattern,
38 const std::uint32_t textLen,
39 const std::uint32_t patternLen);
40 //! @brief Knuth-Morris-Pratt.
41 //! @param text - matching text
42 //! @param pattern - single pattern
43 //! @param textLen - length of matching text
44 //! @param patternLen - length of single pattern
45 //! @return index in matching text
46 static std::int64_t kmp(
47 const unsigned char* const text,
48 const unsigned char* const pattern,
49 const std::uint32_t textLen,
50 const std::uint32_t patternLen);
51 //! @brief Boyer-Moore.
52 //! @param text - matching text
53 //! @param pattern - single pattern
54 //! @param textLen - length of matching text
55 //! @param patternLen - length of single pattern
56 //! @return index in matching text
57 static std::int64_t bm(
58 const unsigned char* const text,
59 const unsigned char* const pattern,
60 const std::uint32_t textLen,
61 const std::uint32_t patternLen);
62 //! @brief Horspool.
63 //! @param text - matching text
64 //! @param pattern - single pattern
65 //! @param textLen - length of matching text
66 //! @param patternLen - length of single pattern
67 //! @return index in matching text
68 static std::int64_t horspool(
69 const unsigned char* const text,
70 const unsigned char* const pattern,
71 const std::uint32_t textLen,
72 const std::uint32_t patternLen);
73 //! @brief Sunday.
74 //! @param text - matching text
75 //! @param pattern - single pattern
76 //! @param textLen - length of matching text
77 //! @param patternLen - length of single pattern
78 //! @return index in matching text
79 static std::int64_t sunday(
80 const unsigned char* const text,
81 const unsigned char* const pattern,
82 const std::uint32_t textLen,
83 const std::uint32_t patternLen);
84
85private:
86 //! @brief Maximum ASCII value.
87 static constexpr std::uint16_t maxASCII{256};
88
89 //! @brief Fill bad character rule table.
90 //! @param badCharRuleTable - bad character rule table
91 //! @param pattern - single pattern
92 //! @param patternLen - length of single pattern
93 static void fillBadCharRuleTable(
94 std::uint32_t badCharRuleTable[], const unsigned char* const pattern, const std::uint32_t patternLen);
95 //! @brief Fill good suffix rule table.
96 //! @param goodSuffixRuleTable - good suffix rule table
97 //! @param pattern - single pattern
98 //! @param patternLen - length of single pattern
99 static void fillGoodSuffixRuleTable(
100 std::uint32_t goodSuffixRuleTable[], const unsigned char* const pattern, const std::uint32_t patternLen);
101 //! @brief Fill the bad character shift table of the Horspool method.
102 //! @param badCharShiftTable - bad character shift table
103 //! @param pattern - single pattern
104 //! @param patternLen - length of single pattern
105 static void fillHorspoolBadCharShiftTable(
106 std::uint32_t badCharShiftTable[], const unsigned char* const pattern, const std::uint32_t patternLen);
107 //! @brief Fill the bad character shift table of the Sunday method.
108 //! @param badCharShiftTable - bad character shift table
109 //! @param pattern - single pattern
110 //! @param patternLen - length of single pattern
111 static void fillSundayBadCharShiftTable(
112 std::uint32_t badCharShiftTable[], const unsigned char* const pattern, const std::uint32_t patternLen);
113};
114} // namespace match
115} // namespace algorithm
116