rollingHashSearch function

int rollingHashSearch(String text, String pattern)

Returns index of pattern in text using rolling hash, or -1.

Implementation

int rollingHashSearch(String text, String pattern) {
  if (pattern.isEmpty) return 0;
  if (pattern.length > text.length) return -1;
  final int patternHash = rollingHash(pattern, 0, pattern.length);
  int textHash = rollingHash(text, 0, pattern.length);
  int pow = 1;
  for (int i = 0; i < pattern.length - 1; i++) {
    pow = (pow * _base) % _mod;
  }
  for (int i = 0; i <= text.length - pattern.length; i++) {
    final int end = i + pattern.length;
    if (end <= text.length &&
        textHash == patternHash &&
        String.fromCharCodes(text.codeUnits.sublist(i, end)) == pattern) {
      return i;
    }
    if (i + pattern.length < text.length) {
      // ignore: saropa_lints/avoid_string_concatenation_loop -- integer rolling-hash arithmetic, not string concatenation
      textHash = (textHash - text.codeUnitAt(i) * pow % _mod + _mod) % _mod;
      // ignore: saropa_lints/avoid_string_concatenation_loop -- integer rolling-hash arithmetic, not string concatenation
      textHash = (textHash * _base + text.codeUnitAt(i + pattern.length)) % _mod;
    }
  }
  return -1;
}