程序员一个月普遍 30-40k，为什么还要去考公拿5-6k，图什么呢

刚才在公司楼下抽烟…风有点大我脑子也嗡嗡的，小李在旁边嘀咕“东哥，给我个算法，已知一个哈希值，怎么在字符串里把那段子串抠出来？”我说等下等下…这个事儿别上头，思路其实很家常。

就是那个…给你一串 s，再给你 base、mod，还有一个 target 哈希，以及长度 k（一般题里会给）。问：s 里有没有长度为 k 的子串，它按同样的哈希规则算出来正好等于 target。有就把位置找出来，最好把子串也顺手带上，对吧。

算法怎么落地

我的习惯是“前缀哈希 + 幂数组”。定义哈希别太玄： hash(s[l..r]) = (Σ (val(s[i]) * base^(i-l))) % mod。 val 我一般用 s[i]-'a'+1 或直接字符的数值。有了前缀哈希 H 和 base 的幂 P，就能 O(1) 拿任意区间哈希： subHash(l,r) = (H[r+1] - H[l] * P[r-l+1]) mod mod。 然后把所有长度为 k 的窗子扫一遍，谁的哈希等于 target 谁上岸。怕碰撞？再做一次字符串直接比对就完了，稳。

我刚在电梯口敲的…别介意变量名有点糙，能跑、清楚就行

publicclassFindSubByHash{

// val 映射，可按题意改；这里直接用字符值（更通用）
privatestaticlongcharVal(char c){
return c;
    }

// 规范化取模，防止负数
privatestaticlongnorm(long x, long mod){
        x %= mod;
return x < 0 ? x + mod : x;
    }

/**
     * 在 s 中查找长度为 k、哈希等于 target 的子串。
     * @param s 文本
     * @param k 子串长度
     * @param base 哈希底数
     * @param mod 取模
     * @param target 目标哈希（与同一规则计算）
     * @return 命中子串；未命中返回 null
     */
publicstatic String findByHash(String s, int k, long base, long mod, long target){
int n = s.length();
if (k <= 0 || k > n) returnnull;

long[] P = newlong[n + 1];   // base 的幂
long[] H = newlong[n + 1];   // 前缀哈希，H[0]=0

        P[0] = 1;
for (int i = 0; i < n; i++) {
            P[i + 1] = (P[i] * base) % mod;
            H[i + 1] = (H[i] * base + charVal(s.charAt(i))) % mod;
        }

long tgt = norm(target, mod);

for (int l = 0; l + k <= n; l++) {
int r = l + k - 1;
long hash = H[r + 1] - (H[l] * P[k]) % mod;
            hash = norm(hash, mod);
if (hash == tgt) {
// 二次校验，防碰撞（可选，但推荐）
                String cand = s.substring(l, r + 1);
if (computeHash(cand, base, mod) == tgt) {
return cand;
                }
            }
        }
returnnull;
    }

// 方便做二次校验：从 0 开始的同规则哈希
publicstaticlongcomputeHash(String t, long base, long mod){
long h = 0;
for (int i = 0; i < t.length(); i++) {
            h = (h * base + charVal(t.charAt(i))) % mod;
        }
return h;
        }

// 小样例随手跑一下
publicstaticvoidmain(String[] args){
        String s = "abracadabra";
int k = 3;
long base = 131, mod = 1_000_000_007L;

// 先算一下 "bra" 的哈希当目标
        String want = "bra";
long target = computeHash(want, base, mod);

        String ans = findByHash(s, k, base, mod, target);
        System.out.println(ans); // 期望输出 "bra"
    }
}

细节

昨天晚上十一点多我还在看日志…哦跑题了。重点几个坑： 1）一致的规则：target 必须用一样的 base、mod、val 定义算出来，不一致你就别怪结果玄学。 2）负数取模：Java 的 % 带符号，减法后要 norm 一下。 3）碰撞：在 mod 比较小或文本很长的场景，命中后做一次字符串直比，成本不大，省心。 4）超长串：n 很大时，这个是 O(n) 扫一遍，内存两个数组也就 O(n)，还行。极限内存就换纯滚动窗写法，也就一丢丢复杂。

行了我得去开会了…谁要把滚动版本也整一下我下班路上给你口述一版，先这么着哈。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html