【模板】字符串哈希

P3370 【模板】字符串哈希

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e4 + 10, M = 1510, P = 131;
int n;
char str[M];
ULL h[M];
vector<ULL> nums;

int main()
{
    cin >> n;
    while(n --)
    {
        scanf("%s", str);

        memset(h, 0, sizeof h);

        int len = strlen(str);
        h[0] = str[0];
        for(int i = 1; i < len; i ++)
            h[i] = h[i -1] * P + str[i];

        nums.push_back(h[len - 1]);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    cout << nums.size() << endl;
}