/**
 * ```
 * RABIN-KARP-MATCHER(T, P, d, q)
 *   n = T.length
 *   m = P.length
 *   h = d^m-1 mod q
 *   p = 0
 *   t_0 = 0
 *
 *   for i = 1 to m               // preprocessing
 *     p = (d * p + P[i]) mod q
 *     t_0 = (d * t_0 + T[i]) mod q
 *
 *   for s = 0 to n - m           // matching
 *     if p == t_s
 *       if P[1..m] == T[s + 1..s + m]
 *         print "Pattern occurs with shift" s
 *     if s < n - m
 *       t_s+1 = (d * (t_s - T[s + 1] * h) + T[s + m + 1]) mod q
 * ```
 */
export function rabinKarpMatcher(
  T: string, // Text
  P: string, // Pattern
  d: number, // Radix
  q: number, // Prime
) {
  const n = T.length;
  const m = P.length;
  const h = d ** (m - 1) % q;
  let p = 0; // Code point of a given letter
  let t = 0; // Code point of a given letter

  // Preprocessing
  for (let i = 0; i < m; i++) {
    p = (d * p + (P.codePointAt(i) ?? 0)) % q;
    t = (d * t + (T.codePointAt(i) ?? 0)) % q;
  }

  // Matching
  for (let s = 0; s <= n - m; s++) {
    if (p === t && P.slice(0, m) === T.slice(s, s + m)) {
      console.log(`Pattern occurs with shift ${s}`);
      return [P.slice(0, m), s];
    }

    if (s < n - m) {
      let newt =
        (d * (t - (T.codePointAt(s) ?? 0) * h) + (T.codePointAt(s + m) ?? 0)) %
        q;

      if (newt < 0) {
        newt += q;
      }

      t = newt;
    }
  }
}

import {expect, test} from "bun:test";
import {rabinKarpMatcher} from "./code.ts";

test(`find pattern "aab" in "acaabc"`, () => {
  const actual = rabinKarpMatcher("acaabc", "aab", 3, 13) ?? [];
  const pattern = actual[0];
  const shift = actual[1];

  expect(pattern).toEqual("aab");
  expect(shift).toEqual(2);
});