字符串

1 - base 前缀 pre[i] : s[1], s[2], ... , s[i] 后缀 suf[i] : s[n-i+1], s[n-i+2], ... , s[n] border : pre[i] == suf[i] border 性质 ： s 的border 的 border 仍为 s 的 border 周期: p s[i] = s[i-p] i > p

性质： p = |s| - border 周期和 border 一一对应

KMP

nxt[i] : pre[i] 的非平凡最长border

构建s2的nxt数组

当适配发生时, 一个naive的做法是仅仅右移1位， 但如果不是周期匹配必定失败 可以加速，找到一个当前匹配一个最小的周期，即最大的 border -> nxt数组进行匹配

时间复杂度： 根据势能分析(即j增减看作势能增减，每次势能至少变化1) O(|n| + |m|)

哈希

多项式哈希 本身无冲突，但是值范围过大，取模后产生冲突

H(base) % mod = H(base) % mod (H(base) - H(base)) % mod = 0

base 为合数， 则存在多个零点， 选一个合数，等价于其中任意一个质因子作为模数

自然溢出

int base = 1313;
ll hash_(string& s) {
    ll ans = 0;
    for(int i = 0; i < s.size(); i++) {
        ans = ans*base + s[i] - 'a' + 1;
    }
    return ans;
}

常用base: 31、131、1313、13131、131313 质数：433、499、599、1000000007 得到子串哈希O(1) 比较一个字符串中的两个子串是否相等的时间复杂度能从O(n)降低到O(1)

int base = 1313;
ll hash_[n+1];
ll power[n+1];
for(int i = 0; i <= s.size(); i++) {
    power[i] = power[i-1]*base;
    hash_[i] = hash_[i-1]*base + s[i] - 'a' + 1;
}
ll hash1 = hash_[r] - hash_[l]*power[r-l+1];

随机base

mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
//jiangly 范围[0,2^64-1]