字符串哈希

核心理解

把字符串看作一个 base 进制数：每读入一个字符，就执行 hash = hash * base + ch。相同字符串一定有相同哈希；不同字符串极小概率碰撞。模板文件用它统计不同字符串数量。

• 复杂度：计算总长度为 L 时是 O(L)；排序去重为 O(n log n)。
• 注意：单哈希有碰撞概率；重要题目可使用双模数，或配合字符串原文二次确认。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define base 131 
signed main()
{
    int n;
    cin>>n;
    string str;
    int zfc[10000000]={0};
    for (int i=0;i<n;i++)
    {
        cin>>str;
        for (int j=0;j<str.size();j++)
        {
            zfc[i]=zfc[i]*base+str[j];
        }
    }
    int ans=0;
    for (int i=0;i<n;i++)
    {
        int find=1;
        for (int j=i+1;j<n;j++)
        {
            if (zfc[i]!=zfc[j]) ;
            else
            {
                find=0;
                break;
            }
        }
        if (find)
        {
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

‍