字符串操作

1.单哈希：进制哈希。进制哈希的核心便是给出一个固定进制base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个base进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同

//整个串hash
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
int base = 131;
string s;
int a[N];
int n;
int get_hash(string s){
    int ans = 0, len = s.length();
    for(int i = 0; i < len; i++){
        ans = (1ll * ans * base + (s[i] - '0')) % mod;
    }
    return ans;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s;
        a[i] = get_hash(s);
        s = "";
    }
    sort(a + 1, a + 1 + n);
    int cnt = 1;
    for(int i = 1; i < n; i++){
        if(a[i] != a[i + 1]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}
//串区间hash
#define ULL unsigned long long
const int N = 100010, base = 131;
ULL h[N]/*前i个字母的哈希值*/, p[N]/*p进制表*/;
//初始化
/*
前缀和公式 h[i+1]=h[i]×P+s[i]h[i+1]=h[i]×P+s[i] i∈[0,n−1]i∈[0,n−1] h为前缀和数组，s为字符串数组
区间和公式 h[l,r]=h[r]−h[l−1]×Pr−l+1
*/
void init(){
    p[0] = 1;
    for(int i = 1; i <= len/*字符串长度*/; i++){
        h[i] = h[i - 1] * base + str[i];
        p[i] = p[i - 1] * base;
    }
}
/*
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上 P^2 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。
*/
ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
    //......
    cin >> str + 1;//从下标为1开始输入
    //......
}

拓展

hash方法：开放寻址法：

#include <bits/stdc++.h>
using namespace std;
const int N = 200010, null = 0x3f3f3f3f;
int h[N];
int find(int x){
    int t = (x % N + N) % N;
    while(h[t] != null && h[t] != x){
        t++;
        if(t == N) t = 0;
    }
    return t;
}
int main(){
    memset(h, 0x3f, sizeof(h));
    scanf("%d", &n);;
    while(n--){
        char ins[2];
        int x;
        scanf("%s%d", &ins, &x);
        if(!strcmp(ins, "I")) h[find(x)] = x;
        else{
            if(h[find(x)] == null) printf("%s\n", "No");
            else printf("%s\n", "Yes");
        }
    }
    return 0;
}

字符串统计

3.trie树

#include <bits/stdc++.h>
const int N = 100010;
int son[N][26], cnt[N], idx;
//插入
void insert(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = str[i].a;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }    
    cnt[p]++;
}
//查询有几个与目标串相同的串
int find(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

4.trie树经典例题：最大异或对

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int ans, a[N];
int son[M][2], idx;
void insert(int x){
    int p = 0;
    for(int i = 30/*数据范围到2^31-1,右移30正好到31位*/; i >= 0; i--){
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int find(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--){
        int u = x >> i & 1;
        if(son[p][!u]){
            res = res * 2 + !u;
            p = son[p][!u];
        }else{
            res = res * 2 + u;
            p = son[p][u];
        }
    }
    return res;
}
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        insert(a[i]);
        int t = find(a[i]);
        ans = max(ans, a[i] ^ t);
    }
    cout << ans << endl;
    return 0;
}

5.KMP

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char p[N]/*模式串*/, s[M]/*匹配串*/;
int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    //求ne
    for(int i = 2/*因为ne[1]一定为0，因为如果执行这段代码(j=ne[1])则说明已经到头了*/, j = 0; i <= n; i++){
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    //kmp匹配
    for(int i = 1, j = 0; i <= m; i++){
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j++;
        if(j == n){
            printf("%d ", i - n);//题中字符串下标从0开始
            j = ne[j];
        }
    }
    return 0;
}