【洛谷P3370】【模板】字符串哈希【哈希】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P3370
给定$N$个字符串（第i个字符串长度为$M[i]$，字符串内包含数字、大小写字母），请求出$N$个字符串中共有多少个不同的字符串。

---

思路：

字符串哈希的模板题。
我用的是单哈希。
把字符串的每一位看成一个$base$进制的数字，用$ans$记录每个字符串的转化后的值，记录在$ha[i]$里。然后将$ha$排序，如果前面和后面的转化后的数字完全一样，那么说明这个字符串有重复，否则就不重复，$sum++$。
要开$unsigned$ $long$ $long$。

---

代码：

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#define prime 10007  //一个质数
using namespace std;

typedef unsigned long long ull;

ull base=177;  //177进制
ull ha[10011];
ull mod=288230376151711743ll;  //模数
ull ans;        
        
int n,len,sum;
string s;

ull hash(int len)
{
	ans=0;
	for (int i=0;i<len;i++)
	 ans=(ans*base+(ull)s[i])%mod+prime;  //转化
	return ans;
}

int main()
{
	ha[0]=-1;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		cin>>s;
		len=s.size();
		ha[i]=hash(len);  //给回hash表
	}
	sort(ha+1,ha+1+n);
	for (int i=1;i<=n;i++)
	 if (ha[i]!=ha[i-1]) sum++;  //不相同就加一
	printf("%d\n",sum);
	return 0;
}