P3370 【模板】字符串哈希

【模板】字符串哈希

题目描述

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

友情提醒：如果真的想好好练习哈希的话，请自觉。

输入格式

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

接下来 N N N 行每行包含一个字符串，为所提供的字符串。

输出格式

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

样例 #1

样例输入 #1

5
abc
aaaa
abc
abcc
12345

样例输出 #1

4

提示

对于 30 % 30\% 30% 的数据： N ≤ 10 N\leq 10 N≤10， M i ≈ 6 M_i≈6 Mi​≈6， M m a x ≤ 15 Mmax\leq 15 Mmax≤15。

对于 70 % 70\% 70% 的数据： N ≤ 1000 N\leq 1000 N≤1000， M i ≈ 100 M_i≈100 Mi​≈100， M m a x ≤ 150 Mmax\leq 150 Mmax≤150。

对于 100 % 100\% 100% 的数据： N ≤ 10000 N\leq 10000 N≤10000， M i ≈ 1000 M_i≈1000 Mi​≈1000， M m a x ≤ 1500 Mmax\leq 1500 Mmax≤1500。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

题目解析：

具体可以参考一下博客 一个是关于哈希表的介绍哈希表

另一个是关于哈希表的基本模版字符串哈希

这个题目与字符串哈希类似 或者比起更简单一点 这个不需要去求出每一个点对应的p进制数字 直接去求一整个字符串对应的哈希值 进行去比较

代码

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

const int N = 10010,P= 131;
int n = 1010;

typedef unsigned long long ULL;

int h[N];//记录每一个字符的哈希值

int x[N];//记录不同数组所对应的哈希值  最后进行比较使用的

char str[N];//存储每一个字符串

ULL get(char str[])
{
	int len = strlen(str);
	for (int i = 1; i <= len; i++)
	{
		h[i] = h[i - 1]*P + str[i];
	}
	return h[len];
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> str;
		x[i] = get(str);//记录输入的字符串对应的hash值
	}
	sort(x + 1,x+n+1);

	int ans = 1;
	for (int i = 1; i < n; i++)
	{
		if (x[i] != x[i + 1]) ans++;
	}
	cout << ans;

	return 0;
}