function buildKMPTable(pattern: string): number[] {
  const table = Array(pattern.length).fill(0);
  let j = 0;
  for (let i = 1; i < pattern.length; i += 1) {
    while (j > 0 && pattern[i] !== pattern[j]) {
      j = table[j - 1];
    }
    if (pattern[i] === pattern[j]) {
      j += 1;
    }
    table[i] = j;
  }
  return table;
}

function kmpSearch(text: string, pattern: string): number[] {
  const table = buildKMPTable(pattern);
  const result: number[] = [];
  let j = 0;

  for (let i = 0; i < text.length; i += 1) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = table[j - 1];
    }
    if (text[i] === pattern[j]) {
      j += 1;
    }
    if (j === pattern.length) {
      result.push(i - j + 1);
      j = table[j - 1];
    }
  }

  return result;
}

function rabinKarp(text: string, pattern: string, base = 256, mod = 1000000007): number[] {
  const n = text.length;
  const m = pattern.length;
  if (m > n) return [];

  const result: number[] = [];
  let patternHash = 0;
  let textHash = 0;
  let h = 1;

  for (let i = 0; i < m - 1; i += 1) {
    h = (h * base) % mod;
  }

  for (let i = 0; i < m; i += 1) {
    patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
    textHash = (textHash * base + text.charCodeAt(i)) % mod;
  }

  for (let i = 0; i <= n - m; i += 1) {
    if (patternHash === textHash) {
      let match = true;
      for (let j = 0; j < m; j += 1) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) result.push(i);
    }

    if (i < n - m) {
      textHash = (textHash - text.charCodeAt(i) * h) % mod;
      textHash = (textHash * base + text.charCodeAt(i + m)) % mod;
      if (textHash < 0) textHash += mod;
    }
  }

  return result;
}

function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return '';
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i += 1) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, -1);
      if (!prefix) return '';
    }
  }
  return prefix;
}