boyerMooreSearch function

int boyerMooreSearch(
  1. String text,
  2. String pattern
)

Boyer-Moore String Search: Returns the index of the first occurrence of pattern in text, or -1 if not found.

Implementation

int boyerMooreSearch(String text, String pattern) {
  if (pattern.isEmpty) return 0;
  final badChar = <String, int>{};
  for (int i = 0; i < pattern.length; i++) {
    badChar[pattern[i]] = i;
  }
  int shift = 0;
  while (shift <= text.length - pattern.length) {
    int j = pattern.length - 1;
    while (j >= 0 && pattern[j] == text[shift + j]) {
      j--;
    }
    if (j < 0) return shift;
    shift += (j - (badChar[text[shift + j]] ?? -1)).clamp(1, pattern.length);
  }
  return -1;
}