Rabin-Karp String Search Algoritması

1function rabinKarpSearch(text: string, pattern: string): number {
2  if (pattern.length === 0) return 0;
3  if (pattern.length > text.length) return -1;
4  const base = 256, prime = 1_000_000_007, patternLength = pattern.length;
5  let highBase = 1, patternHash = 0, windowHash = 0;
6  for (let index = 0; index < patternLength - 1; index += 1) {
7    highBase = (highBase * base) % prime;
8  }
9  for (let index = 0; index < patternLength; index += 1) {
10    patternHash = (patternHash * base + pattern.charCodeAt(index)) % prime;
11    windowHash = (windowHash * base + text.charCodeAt(index)) % prime;
12  }
13  for (let start = 0; start <= text.length - patternLength; start += 1) {
14    if (patternHash === windowHash && text.slice(start, start + patternLength) === pattern) {
15      return start;
16    }
17    if (start < text.length - patternLength) {
18      const removed = text.charCodeAt(start) * highBase;
19      const added = text.charCodeAt(start + patternLength);
20      windowHash = (windowHash - removed) % prime;
21      windowHash = (windowHash + prime) % prime;
22      windowHash = (windowHash * base + added) % prime;
23    }
24  }
25  return -1;
26}