1const BASE = 131, MOD = 1000003;
2function buildHash(s) {
3 const h = [0], pw = [1];
4 for (let i = 0; i < s.length; i++) {
5 h[i+1] = (h[i] * BASE + s.charCodeAt(i)) % MOD;
6 pw[i+1] = (pw[i] * BASE) % MOD;
7 }
8 return { h, pw };
9}
10function subHash(h, pw, l, r) { // 子串 s[l..r] 哈希
11 return ((h[r+1] - h[l] * pw[r-l+1]) % MOD + MOD) % MOD;
12}
13function rabinKarp(s, pat) {
14 const { h, pw } = buildHash(s);
15 const patHash = buildHash(pat).h[pat.length];
16 for (let i = 0; i + pat.length <= s.length; i++)
17 if (subHash(h, pw, i, i + pat.length - 1) === patHash)
18 matches.push(i); // 哈希相等则可能匹配
19}