字符串哈希

单哈希

#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e4 + 9;
int d[MAXn], sha[MAXn];
const int BASE = 1331, P = 1e9 + 9;

int fsha(string s) {
    int len = s.length();
    int ans = 1;
    for(int i = 0; i < len; i ++)
        ans = (ans * BASE + s[i]) % P;
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    string str;
    getline(cin, str);
    for(int i = 1; i <= n; i ++) {
        getline(cin, str);
        sha[i] = fsha(str);
    }
    sort(sha + 1, sha + n + 1);
    printf("%d", unique(sha + 1, sha + n + 1) - sha - 1);
    return 0;
}

双哈希

#include <bits/stdc++.h>
using namespace std;
const int Base1 = 1331, P1 = 1e9 + 7;
const int Base2 =  131, P2 = 1e9 + 9;
const int MAXl = 1e6 + 9;
int h1[MAXl], h2[MAXl], b1[MAXl], b2[MAXl];

pair<int, int> fsha(int l, int r) {
    int f1 = (h1[r] - 1ll * h1[l - 1] * b1[r - l + 1] % P1 + P1) % P1;
    int f2 = (h2[r] - 1ll * h2[l - 1] * b2[r - l + 1] % P2 + P2) % P2;
    return {f1, f2};
}

int main() {
    h1[0] = h2[0] = b1[0] = b2[0] = 1;
    for(int i = 1; i <= len; i ++) {
        h1[i] = (1ll * h1[i-1] * Base1 + str[i]) % P1;
        h2[i] = (1ll * h2[i-1] * Base2 + str[i]) % P2;
        b1[i] = (1ll * b1[i-1] * Base1) % P1;
        b2[i] = (1ll * b2[i-1] * Base2) % P2;
    }
    return 0;
}