1 介绍与基础实现

字符串哈希就是把一个任意长度的字符串映射成一个非负整数，并且冲突概率几乎为0。KMP 相比于该方法，除了在计算字符串循环节时候有优势，这个方法完爆KMP。

如何做：取一个固定值 P （经验来说通常取 131 和 13331， 此时概率极低），把字符串看作是 P 进制数， 取一个固定值 M， 改 P 进制数对 M 取余，就是改字符串的HASH值。

如果HASH值相等，通常可以认为两个串是相等的。通常 M 取 2642^{64}, 可以直接用 unsigned long long 来存储这个HASH 值，在计算的时候不处理算数溢出的问题，因为对于 unsigned 数值，溢出的时候相当于对 2642^{64} 取模，这样就可以避免低效的取模运算了。

假设我们已经算出了字符串的前缀哈希值，第 i 位记为 h(i)h(i)，我们就可以计算一个子串的HASH值，下图是证明(计算 l,rl, r 子串的HASH值)：

已知 ：h(i)=s(1)∗Pi−1+s(2)∗Pi−2+...+s(i)∗P0h(i) = s(1) * P^{i-1} + s(2) * P^{i-2} + ... + s(i) * P^0

对于 l−1l-1的串: h(l−1)=s(1)∗Pl−2+s(2)∗Pl−3+...+s(l−1)∗P0h(l-1) = s(1) * P^{l-2} + s(2) * P^{l-3} + ... + s(l-1) * P^0

对于 rr 的串: h(r)=s(1)∗Pr−1+s(2)∗Pr−2+...+s(r)∗P0h(r) = s(1) * P^{r-1} + s(2) * P^{r-2} + ... + s(r) * P^0

那么 [l,r][l,r] 的串的 HASH 值为 h(r)−h(l−1)∗Pr−l+1h(r) - h(l-1) * P^{r-l+1}

下面是代码实现：

typedef unsigned long long ULL; 

const int N = 1e5 + 10;

// 一般取 131 、13331
const int P = 131;

// p[i] 代表 p的i次方
// h[i] 代表前 i 个字符的HASH值
ULL p[N], h[N];

// 实现
ULL get(int l, int r) {
    return h[r] - h[l-1] * p[r-l+1];
}

// 算出前缀HASH值
void build(string s) {
  // p^0 = 1
  p[0] = 1;
  for(int i=1;i<=n;i++) {
    p[i] = p[i-1] * P;
    h[i] = h[i-1] * P + s[i-1];
  }
}

int main() {
  cin >> s;
  build(s);
  int l1, r1, l2, r2;
  cin >> l1 >> r1 >> l2 >> r2;
  cout << get(l1, r1) == get(l2, r2);
  return 0;
}

2 例题实现

1. 兔子与兔子

很久很久以前，森林里住着一群兔子。

有一天，兔子们想要研究自己的 DNA 序列。

我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。

然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。

注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式

第一行输入一个 DNA 字符串 S。

第二行一个数字 m，表示 m 次询问。

接下来 m 行，每行四个数字 l1,r1,l2,r2，分别表示此次询问的两个区间，注意字符串的位置从 1 开始编号。

输出格式

对于每次询问，输出一行表示结果。

如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）。

数据范围

1≤length(S),m≤1000000

输入样例：

aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

代码实现

分析 ： 很明显，这题就是字符串hash裸题，直接用上方的模板就好了。

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e6 + 10, P = 131;

ULL p[N], h[N];

void build(string s) {
    p[0] = 1;
    for(int i=1;i<=s.size();i++) {
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + s[i-1];
    }
}

ULL get(int l, int r) {
    return h[r] - h[l-1] * p[r - l + 1];
}

int main() {
    string s;
    cin >> s;
    build(s);
    int m;
    cin >> m;
    while(m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

2.回文子串的最大长度

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为 N 的字符串 S，求他的最长回文子串的长度是多少。

输入格式

输入将包含最多 30 个测试用例，每个测试用例占一行，以最多 1000000 个小写字符的形式给出。

输入以一个以字符串 END 开头的行表示输入终止。

输出格式

对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

输入样例：

abcbabcbabcba
abacacbaaaab
END

输出样例：

Case 1: 13
Case 2: 6

代码实现

分析：这题字符串太长区间DP空间爆炸，可以使用马拉车算法求解，这里介绍的主要是 二分 + 字符串HASH 的方法

对于二分 ：我们要将 奇数串 与 偶数串 分开二分（这个很重要）

对于字符串HASH ：我们只需要维护字符串正 h1、反 h2 数组即可，对于回文来讲，正反都一样

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10, P = 131;

#define Debug(in) cout<<#in<<"="<<(in)<<endl

typedef unsigned long long ULL;

int n;

ULL p[N], h[N], h_rev[N]; 

void build(string s) {
    p[0] = 1;
    h[0] = 0, h_rev[s.size() + 1] = 0;
    for(int i=1;i<=s.size();i++) {
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + s[i-1];
    }
    for(int i=s.size();i>=1;i--) {
        h_rev[i] = h_rev[i+1] * P + s[i-1];
    }
}

ULL get(int l, int r) {
    return h[r] - h[l-1] * p[r - l + 1];
}

ULL get_rev(int l, int r) {
    return h_rev[l] - h_rev[r+1] * p[r-l + 1];
}

bool find(int sz) {
    // Debug(sz);
    if(sz == 1) return true;
    for(int i=1;i<=n;i++) {
        int l = i, r = i + sz - 1;
        if(r > n) break;
        if(get(l, r) == get_rev(l, r)) {
           return true;
        }
    }
    return false;
}

int main() {
    string s;
    int caseNum = 0;
    
    vector<int> odds;
    vector<int> evens;
    for(int i=1;i<N;i++) {
        if(i & 1) odds.push_back(i);
        else evens.push_back(i);
    }
    while(cin >> s, s != "END") {
        
        build(s);
        int ans = 1;
        n = s.size();
        int k;
        // odd
        if(n & 1) k = n;
        else k = n - 1;
        int l = 0, r = lower_bound(odds.begin(), odds.end(), k) - odds.begin();
        while(l<=r) {
            int mid = (l + r) >> 1;
            bool b = find(odds[mid]);
            if(b) ans = max(ans, odds[mid]), l = mid + 1;
            else r = mid - 1;
        }
        
        // even
        if(n & 1) k = n - 1;
        else k = n;
        l = 0, r = lower_bound(evens.begin(), evens.end(), k) - evens.begin();
        while(l<=r) {
            int mid = (l + r) >> 1;
            bool b = find(evens[mid]);
            if(b) ans = max(ans, evens[mid]), l = mid + 1;
            else r = mid - 1;
        }
        
        printf("Case %d: %d\n", ++caseNum, ans);
    }
    
    return 0;
}