想学习一下字符串哈希结果发现以前自己已经脑补出来用过了啊？虽然base和mod取的不是那么好…

参考资料：https://wenku.baidu.com/view/b7d3d1c6804d2b160a4ec090

hash函数：$hash[i]=(hash[i-1]*p+idx(s[i]))\%mod$。

子串的hash值（下标从1开始）：$hash[l,r]=(hash[r]-hash[l-1]*p^{r-l+1})\%mod$。

获取哈希值的函数用inline似乎会快一点。

以求N个字符串中有多少个不同的字符串为例存个模板（这里的排序用set替代也是可以的）：

自然溢出（最快）：

typedef unsigned long long ull;
const ull base=131;
char a[2000];
ull temp[10010];
ull solve()
{
    int len=strlen(a);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=ans*base+(ull)a[i];//这里有时候不必要的剪枝就不要剪了啊
    return ans&0x7fffffff;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",a);
        temp[i]=solve();
    }
    sort(temp,temp+n);
    int ans=1;
    for(int i=1;i<n;i++)
    {
        if(temp[i]!=temp[i-1])
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

用$10^{18}$的大质数取模：

typedef unsigned long long ull;
const ull base=131;
const ull mod=212370440130137957ll;
char a[2000];
ull temp[10010];
ull solve()
{
    int len=strlen(a);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)a[i])%mod;
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",a);
        temp[i]=solve();
    }
    sort(temp,temp+n);
    int ans=1;
    for(int i=1;i<n;i++)
    {
        if(temp[i]!=temp[i-1])
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

双哈希（最保险）：

typedef unsigned long long ull;
const ull base=131;
const ull mod1=19260817;
const ull mod2=19660813;
char a[2000];
struct node
{
    ull x,y;
}temp[10010];
ull solve(ull p)
{
    int len=strlen(a);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)a[i])%p;
    return ans;
}
bool cmp(node aa,node bb)
{
    if(aa.x!=bb.x)return aa.x<bb.x;
    return aa.y<bb.y;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",a);
        temp[i].x=solve(mod1);
        temp[i].y=solve(mod2);
    }
    sort(temp,temp+n,cmp);
    int ans=1;
    for(int i=1;i<n;i++)
    {
        if(temp[i].x!=temp[i-1].x||temp[i].y!=temp[i-1].y)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

手写哈希表（拉链法）：

const int mod=4000007;
int cnt=0;
memset(head,-1,sizeof(head));
bool used(ull x)//手写拉链法哈希
{
    int temp=x%mod;
    for(int i=head[temp];i!=-1;i=nxt[i])
        if(val[i]==x)return true;
    val[++cnt]=x;
    nxt[cnt]=head[temp];
    head[temp]=cnt;
    return false;
}