This is an implementation of the Knuth-Morris-Pratt algorithm
| 1220 | |
| 1221 | // This is an implementation of the Knuth-Morris-Pratt algorithm |
| 1222 | struct 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 | |
| 1273 | struct PlainStartsWithMatcher { |
| 1274 | const MatchSubstringOptions& options_; |