位运算 + 滚动哈希实现轻量文本搜索引擎

// 运行环境：Node.js 14+
// 保存为 dsa-l26.js，执行：node dsa-l26.js

// 用位掩码表示集合：第 i 位=1 表示元素 i 在集合内
function setOps() {
  let A = 0, B = 0
  for (const i of [0, 2, 4]) A |= (1 << i) // 加入元素
  for (const i of [1, 2, 3]) B |= (1 << i)
  const union = A | B          // 并集
  const inter = A & B          // 交集
  const diff = A & ~B          // 差集（在 A 不在 B）
  return { union, inter, diff }
}
console.log(setOps()) // { union: 31, inter: 4, diff: 21 }
// 解释：A={0,2,4}=bits 10101=21, B={1,2,3}=bits 01110=14
// union=31(11111), inter=4(00100=元素2), diff=21(10101=元素0,2,4)

// 两个集合相似度（Jaccard）：交集大小 / 并集大小
function jaccard(a, b) {
  const inter = (a & b).toString(2).split('').filter(c => c === '1').length
  const union = (a | b).toString(2).split('').filter(c => c === '1').length
  return union ? inter / union : 0
}
console.log(jaccard(21, 14).toFixed(2)) // 0.20（交集1个/并集5个）

// 在文本 txt 中找出所有出现模式 pat 的起始下标
function rabinKarp(txt, pat) {
  const base = 131, mod = 1e9 + 7
  const m = pat.length, n = txt.length
  if (m > n) return []
  const pow = (() => { let p = 1; for (let i = 0; i < m - 1; i++) p = (p * base) % mod; return p })()
  const hash = s => { let h = 0; for (const ch of s) h = (h * base + ch.charCodeAt(0)) % mod; return h }
  const ph = hash(pat)
  let th = hash(txt.slice(0, m))
  const res = []
  if (th === ph && txt.slice(0, m) === pat) res.push(0)
  for (let i = m; i < n; i++) {
    // 滑出 txt[i-m]，滑入 txt[i]
    th = (th - txt.charCodeAt(i - m) * pow % mod + mod) % mod
    th = (th * base + txt.charCodeAt(i)) % mod
    if (th === ph && txt.slice(i - m + 1, i + 1) === pat) res.push(i - m + 1)
  }
  return res
}
console.log(rabinKarp('abracadabra', 'abra')) // [0, 7]