Knuth-Morris-Pratt String Search Algoritması

1function buildLps(pattern: string): number[] {
2  const lps = Array(pattern.length).fill(0);
3  let length = 0;
4  let index = 1;
5
6  while (index < pattern.length) {
7    if (pattern[index] === pattern[length]) {
8      length += 1;
9      lps[index] = length;
10      index += 1;
11    } else if (length > 0) {
12      length = lps[length - 1];
13    } else {
14      lps[index] = 0;
15      index += 1;
16    }
17  }
18
19  return lps;
20}
21
22function kmpSearch(text: string, pattern: string): number {
23  if (pattern.length === 0) return 0;
24
25  const lps = buildLps(pattern);
26  let textIndex = 0;
27  let patternIndex = 0;
28
29  while (textIndex < text.length) {
30    if (text[textIndex] === pattern[patternIndex]) {
31      textIndex += 1;
32      patternIndex += 1;
33
34      if (patternIndex === pattern.length) {
35        return textIndex - patternIndex;
36      }
37    } else if (patternIndex > 0) {
38      patternIndex = lps[patternIndex - 1];
39    } else {
40      textIndex += 1;
41    }
42  }
43
44  return -1;
45}