P2580 于是他错误的点名开始了 • CoderXL's Blog

思考一下：一个名字是长度小于等于 $50$ 的小写字母序列，那么可能的名字数量有 $(26^{51}-26)/25$ 个，值域非常大。但是题目中会出现的名字总数只有 $10^4$ ，这符合值域大+稀疏的特征，适合使用哈希。

使用 STL 的 map 或 set 可以轻松通过此题，但是为了掌握哈希的代码实现，以便未来解决更难的问题，有必要练习手写哈希。

字符串哈希#

一个朴素的想法是把字符串当成一个超长 $p$ 进制整数（本题 $p$ 可以取大于等于 $27$ 的整数），将字母映射到数位，然后在某个模数 $m$ 下计算出这个整数的余数，当作这个字符串的哈希值。

一个常用的实现方式是使用 unsigned long long 来对 $2^{64}$ 自然溢出取模：

int p=131;
unsigned long long hash_value=0;
for(int i=0;i<s.length();i++)hash_value=hash_value*p+s[i];

cpp

这种方法计算一个长度为 $S$ 的字符串的哈希值，复杂度是 $O(S)$ . 本题 $S\le 50$ 可视作常数。

但是对于这道题，我们需要的是一种能够以字符串为键快速查询一些数据的办法。这意味着我们可能需要以哈希值为下标开一个数组 $id$ 来指向那些数据，因此哈希值的范围应当在数组大小的可接受范围之内（一般来说， $10^6 \sim 10^7$ 以下可行）。

所以我们手动选择一个模数，比如 $m=1000003$ ，然后每次对它取模。计算出一个字符串 $s$ 的哈希值 $h(s)$ 之后，就可以让 $id_{h(s)}$ 指向 $s$ 对应的数据，对于本题，这些数据就是 “名字 $s$ ” 是否在名单中出现过、被教练点到了几次。

但是，任何哈希都不能避免哈希冲突。为此，我们可以给每个哈希值预留 $10$ 个空位。我们期望：几乎不可能有多于 10 个字符串都计算为同一个哈希值。实际上，由于我们的模数和进制数都是随机选取且性质良好，这种情况确实几乎不可能发生。

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, MOD = 1000003, P = 131;

int n,m;
string s[N];
int num[N];
int hs[10][MOD+10],cnt[MOD+10];

int get_h(const string&x)
{
    int ret=0;
    for(int i=0;i<x.length();i++)
    {
        ret=ret*P+x[i];
        ret%=MOD;
    }
    return ret;
}
int main()
{
    cin>>n;
    int hash_v;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        hash_v=get_h(s[i]);
        hs[cnt[hash_v]++][hash_v]=i;
    }
    cin>>m;
    string tmp;
    for(int i=1;i<=m;i++)
    {
        cin>>tmp;
        hash_v=get_h(tmp);
        for(int j=0,id;j<cnt[hash_v];j++)
        {
            id=hs[j][hash_v];
            if(s[id]==tmp)
            {
                if(num[id]==0)cout<<"OK\n";
                else cout<<"REPEAT\n";
                num[id]++;
                goto done;
            }
        }
        cout<<"WRONG\n";
    done:;
    }
    return 0;
}

cpp

为了进一步降低出错的概率，可以考虑使用两组甚至多组模数和进制数，进行“双哈希”。

复杂度 $O((n+m)S)$ .

字典序+二分#

既然任务是“查找”，我们永远可以祭出单调性+二分查找的范式。实际上，字符串之间有良定义的序，称为字典序。

按照字典序比较两个字符串的大小关系，设二者的长度为 $S_1,S_2$ ，则复杂度是 $O(\min(S_1,S_2))$ .

一旦将题目中所有的名字按照字典序升序排列，那么查找一个字符串就只需在其中二分即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n,m;
string s[N];
int num[N];

int find(const string&x)
{
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(s[mid]<x)
        {
            l=mid+1;
        }
        else
        {
            r=mid;
        }
    }
    return l;
}

int main()
{
    cin>>n;
    int hash_v;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    sort(s+1,s+n+1);
    cin>>m;
    string tmp;
    for(int i=1;i<=m;i++)
    {
        cin>>tmp;
        int id=find(tmp);
        if(s[id]==tmp)
        {
            if(num[id]==0)cout<<"OK\n";
            else cout<<"REPEAT\n";
            num[id]++;
            continue;
        }
        cout<<"WRONG\n";
    }
    return 0;
}

cpp

复杂度 $O((n+m)S\log n)$ .

后记#

本题正解为 Trie，感兴趣的同学可自行了解，是一个空间复杂度更低、不存在冲突、添加和查询字符串的时间复杂度均为 $O(S)$ 的数据结构。

但如你所见，相当数量的字符串题目都可以使用哈希（或者说经过巧妙设计的哈希）解决，无论题目原本正解是什么。此外，在解决其他问题时，灵活运用哈希也十分重要。