哈希


例题 - Finding Periods CSES - 普及+/提高
例题 - 请努力完成本题，再阅读以下内容。	解答

哈希（hashing）也叫散列，是用来快速判断数据（例如字符串）之间是否相同的方法。在哈希中，我们不是一个个比较字节（字符），而是比较两个串的哈希值。

字符串 $s$ 的多项式哈希如下：

(\texttt{s}[0]A^{n-1}+\texttt{s}[1]A^{n-2}+...+\texttt{s}[n]) \mod M

常数的常见值： $A=911382323$ , $M=972663749$ ，或者更容易记忆的： $A=69420$ , $M=10^9+9$ 。

有时我们需要快速计算 $S$ 的任意子串的哈希，这时可以预处理 $\texttt{h}[]$ 和 $\texttt{p}[]$ ：

\texttt{h}[0] = \texttt{s}[0] \\ \texttt{h}[k] = (\texttt{h}[k-1]A + \texttt{s}[k]) \mod M \\ \texttt{p}[0] = 1 \\ \texttt{p}[k] = \texttt{p}[k-1]A \mod M

则 $S[a:b]$ 的哈希值为：

(\texttt{h}[b] - \texttt{p}[b-a+1] \cdot \texttt{h}[a-1]) \mod M

资源
CPH	26.3 - String Hashing
OI-Wiki	字符串哈希

题解 - Finding Periods

我们可以逐一测试所有可能的周期（ $1 .. n$ ），那么总共需要的子字符串次数是 $n(1+\frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n})$ ，括号内是一个调和级数，所以总比较次数大小规模为 $n \ln n$ ，如果比较子字符串相等的操作是 $\mathcal{O}(1)$ 的（通过哈希达到），则整个算法为 $\mathcal{O}(n \log n)$ 。

下面算法中加了一步倍增的优化（len *= 2），复杂度更低一些，不加这个优化也是可以的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
const int MAXN = 1000005;
char s[MAXN];
int M = 972663749;
int A = 911382323;
int h[MAXN], p[MAXN];
 
int hsh(int a,int b) {     // [a,b]
    int res;
    if (a == 0) res = h[b];
    else res = (h[b] - (ll)h[a-1]*p[b-a+1] + (ll)h[a-1]*M) % M;
    return res;
}
 
int main() {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; i++) {
        h[i] = i ? ((ll)h[i-1] * A + s[i]) % M : s[0];
        p[i] = i ? ((ll)p[i-1]*A)%M : 1;
    }
    for (int i = 1; i < n; i++) {   // test i as period
        bool ok = true;
        for (int len = i; len < n; len *= 2) {
            int len2 = min(n-len, len);
            if (hsh(0, len2-1) != hsh(len, len+len2-1)) {
                ok = false;
                break;
            }
        }
        if (ok) printf("%d ", i);
    }
    printf("%d", n);
 
    return 0;
}

习题
P4656	CEOI	Palindromic Partitions	2017	普及+/提高	解答
P3667	USACO Gold	Lights Out	2016	普及+/提高	解答
CF427D	CF	Palindromic Characteristics	2017	普及+/提高	解答
CF	CF	Check Transmission		普及+/提高	解答
P4824	USACO Silver	Censoring	2015	提高+/省选-	解答
P3667	USACO Gold	Bovine Genomics	2017	提高+/省选-	解答
P7538	COCI	Osmosmjerka	2016	提高+/省选-	解答