本文共 1655 字，大约阅读时间需要 5 分钟。

$$字符串哈希$$

题目链接：

题目

如题，给定$N$个字符串（第$i$个字符串长度为$Mi$，字符串内包含数字、大小写字母，大小写敏感），请求出$N$个字符串中共有多少个不同的字符串。

输入

第一行包含一个整数$N$，为字符串的个数。

输出

输出包含一行，包含一个整数，为不同的字符串个数。

样例输入

5abcaaaaabcabcc12345

样例输出

4

样例解释

样例中第一个字符串$(abc)$和第三个字符串$(abc)$是一样的，所以所提供字符串的集合为$\{$

数据范围

对于$30\%$的数据：$N<=10，Mi\approx 6，Mmax<=15$;

思路

这道题就是字符串Hash的模板，没什么好说的。

代码

#include
   
    #include
    
     #define ll long longusing namespace std;ll n, a, f[10001], p = 67, len, ans;char b[1001];ll qsm(ll i, ll j) {   //快速幂	ll an = 1;	while (j) {   		if (j & 1) an = an * i;		i = i * i;		j >>= 1;	}	return an;}ll hs(ll i) {   //哈希	if (b[i] >= '0' && b[i] <= '9') return (b[i] - 48) * qsm(p, i);	if (b[i] >= 'A' && b[i] <= 'Z') return (b[i] - 55) * qsm(p, i);	return (b[i] - 61) * qsm(p, i);}int main() {   	scanf("%lld", &n);//读入		for (ll i = 1; i <= n; i++) {   		getchar();//处理换行符		scanf("%s", &b);//读入		len = strlen(b);//求出字符串长度		a = 0;//初始化		for (ll i = 0;i < len; i++)			a += hs(i);//求出此字符串的哈希值		bool yes = 0;//初始化		for (ll i = 1; i <= ans; i++)			if (a == f[i]) {   //判断是否与前面的字符串有相同的				yes = 1;//标记				break;//退出			}		if (!yes) {   //是否是新的字符串			ans++;//不同的字符串数增加			f[ans] = a;//记录下来		}	}		printf("%lld", ans);//输出		return 0;}