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