MCPcopy Create free account
hub / github.com/apache/arrow / PlainSubstringMatcher

Class PlainSubstringMatcher

cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:1222–1271  ·  view source on GitHub ↗

This is an implementation of the Knuth-Morris-Pratt algorithm

Source from the content-addressed store, hash-verified

1220
1221// This is an implementation of the Knuth-Morris-Pratt algorithm
1222struct PlainSubstringMatcher {
1223 const MatchSubstringOptions& options_;
1224 std::vector<int64_t> prefix_table;
1225
1226 static Result<std::unique_ptr<PlainSubstringMatcher>> Make(
1227 const MatchSubstringOptions& options) {
1228 // Should be handled by partial template specialization below
1229 DCHECK(!options.ignore_case);
1230 return std::make_unique<PlainSubstringMatcher>(options);
1231 }
1232
1233 explicit PlainSubstringMatcher(const MatchSubstringOptions& options)
1234 : options_(options) {
1235 // Phase 1: Build the prefix table
1236 const auto pattern_length = options_.pattern.size();
1237 prefix_table.resize(pattern_length + 1, /*value=*/0);
1238 int64_t prefix_length = -1;
1239 prefix_table[0] = -1;
1240 for (size_t pos = 0; pos < pattern_length; ++pos) {
1241 // The prefix cannot be expanded, reset.
1242 while (prefix_length >= 0 &&
1243 options_.pattern[pos] != options_.pattern[prefix_length]) {
1244 prefix_length = prefix_table[prefix_length];
1245 }
1246 prefix_length++;
1247 prefix_table[pos + 1] = prefix_length;
1248 }
1249 }
1250
1251 int64_t Find(std::string_view current) const {
1252 // Phase 2: Find the prefix in the data
1253 const auto pattern_length = options_.pattern.size();
1254 int64_t pattern_pos = 0;
1255 int64_t pos = 0;
1256 if (pattern_length == 0) return 0;
1257 for (const auto c : current) {
1258 while ((pattern_pos >= 0) && (options_.pattern[pattern_pos] != c)) {
1259 pattern_pos = prefix_table[pattern_pos];
1260 }
1261 pattern_pos++;
1262 if (static_cast<size_t>(pattern_pos) == pattern_length) {
1263 return pos + 1 - pattern_length;
1264 }
1265 pos++;
1266 }
1267 return -1;
1268 }
1269
1270 bool Match(std::string_view current) const { return Find(current) >= 0; }
1271};
1272
1273struct PlainStartsWithMatcher {
1274 const MatchSubstringOptions& options_;

Callers 2

ExecMethod · 0.85
ExecMethod · 0.85

Calls

no outgoing calls

Tested by

no test coverage detected