演算法

1const utf8 = (s: string) => Array.from(new TextEncoder().encode(s));
2 
3function bruteForce(text: string, pattern: string): number[] {
4  const t = utf8(text), p = utf8(pattern), found: number[] = [];
5  if (p.length === 0) return found; // Empty means no active search.
6  for (let s = 0; s + p.length <= t.length; s++) {
7    let j = 0;
8    while (j < p.length && t[s + j] === p[j]) j++;
9    if (j === p.length) found.push(s);
10  }
11  return found;
12}
13 
14// fail[q]: length of the longest proper prefix of p[0..q] that is also its suffix.
15function failureTable(p: number[]): number[] {
16  const fail = new Array(p.length).fill(0);
17  let k = 0;
18  for (let q = 1; q < p.length; q++) {
19    while (k > 0 && p[q] !== p[k]) k = fail[k - 1];
20    if (p[q] === p[k]) k++;
21    fail[q] = k;
22  }
23  return fail;
24}
25 
26function kmp(text: string, pattern: string): number[] {
27  const t = utf8(text), p = utf8(pattern), found: number[] = [];
28  if (p.length === 0) return found;
29  const fail = failureTable(p);
30  let j = 0;
31  for (let i = 0; i < t.length; i++) {
32    while (j > 0 && t[i] !== p[j]) j = fail[j - 1];
33    if (t[i] === p[j]) j++;
34    if (j === p.length) {
35      found.push(i - p.length + 1);
36      j = fail[j - 1];
37    }
38  }
39  return found;
40}
41 
42function rabinKarp(text: string, pattern: string, mod: number): number[] {
43  const t = utf8(text), p = utf8(pattern), m = p.length, found: number[] = [];
44  if (m === 0 || m > t.length) return found;
45  let high = 1;
46  for (let k = 1; k < m; k++) high = (high * 256) % mod;
47  let ph = 0, wh = 0;
48  for (let k = 0; k < m; k++) {
49    ph = (ph * 256 + p[k]) % mod;
50    wh = (wh * 256 + t[k]) % mod;
51  }
52  for (let s = 0; s + m <= t.length; s++) {
53    if (wh === ph) {
54      let j = 0;
55      while (j < m && t[s + j] === p[j]) j++;
56      if (j === m) found.push(s);
57    }
58    if (s + m < t.length) {
59      wh = (((wh - (t[s] * high) % mod + mod) % mod) * 256 + t[s + m]) % mod;
60    }
61  }
62  return found;
63}