题解 P3370 【【模板】字符串哈希】

· · 题解

ELF\ Hash

我们先看一个最简单的错位叠加哈希：

inline uint hs(char *s){
    reg uint sm=0;
    reg char *p=s;
    while(*p)sm=(sm<<4)+*p++;
    return (sm&0x7fffffff);
}

但是这个哈希函数显然可能会溢出，从而增加冲突的可能性。

为了防止溢出，可以利用一个辅助变量x，每次更新哈希值的时候执行以下操作：

(x=sm&0xf0000000)&&(sm^=(x>>24),sm&=~x);
//为了压行+卡常数进行了改写，实际上等同如下代码：
x=sm;
if(x&0xf0000000)sm^=(x>>24),sm&=~x;

它的意义是：取x的可能溢出的最高一位，若不为零则有溢出风险，这时最简单的方式就是直接暴力地把溢出的内容转移到低位，这样既可保证每一位都对hash值有影响。

可以证明，这样的哈希方式正确率是极高的。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef unsigned int uint;
uint hsh[10001],ans=1,n;
static char str[10001];
inline uint hs(char *s){
    reg uint sm=0,x=0;
    reg char *p=s;
    while(*p)
        sm=(sm<<4)+*p,
        (x=sm&0xf0000000)&&(sm^=(x>>24),sm&=~x),
        ++p;
    return (sm&0x7fffffff);
}
int main(){
    freopen("1.in","r",stdin);
    scanf("%d",&n);
    for(reg int i=1;i<=n;++i)
        scanf("%s",str),hsh[i]=hs(str);
    sort(hsh+1,hsh+n+1);
    for(reg int i=1;i<n;++i)
        ans+=hsh[i]!=hsh[i+1];
    printf("%d",ans);
    return 0;
}