// rapidfuzz.fuzz.ratio 的替身：归一化的 Indel 相似度 × 100。
// Indel 距离 = 只允许插入、删除时的编辑距离 = len(a) + len(b) − 2 × LCS(a, b)，
// ratio = (1 − 距离 / (len(a) + len(b))) × 100 = 200 × LCS / (len(a) + len(b))。
// 两个都是空串时 rapidfuzz 回 100。按 Unicode 码点比，与 Python 的 str 一致。

export function lcsLength(a: readonly string[], b: readonly string[]): number {
  if (a.length === 0 || b.length === 0) return 0;
  // 滚动一行的 DP，O(len(a) × len(b)) 时间、O(len(b)) 空间；这里比较的都是几百字以内的短文本。
  let prev = new Uint32Array(b.length + 1);
  let cur = new Uint32Array(b.length + 1);
  for (let i = 1; i <= a.length; i++) {
    const ai = a[i - 1];
    for (let j = 1; j <= b.length; j++) {
      cur[j] = ai === b[j - 1] ? prev[j - 1]! + 1 : Math.max(prev[j]!, cur[j - 1]!);
    }
    [prev, cur] = [cur, prev];
    cur.fill(0);
  }
  return prev[b.length]!;
}

export function ratio(s1: string, s2: string): number {
  const a = Array.from(s1);
  const b = Array.from(s2);
  const total = a.length + b.length;
  if (total === 0) return 100;
  return (200 * lcsLength(a, b)) / total;
}