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

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

5 abc aaaa abc abcc 12345

输出 #1复制

4

说明/提示

数据范围

对于 30% 的数据：N≤10，Mi​≈6，Mmax​≤15。

对于 70% 的数据：N≤1000，Mi​≈100，Mmax​≤150。

对于 100% 的数据：N≤10000，Mi​≈1000，Mmax​≤1500。

样例说明

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

#include<bits/stdc++.h> using namespace std; const int N=10010,P=131; int n; typedef unsigned long long ULL; ULL a[N]; ULL get_hash(string s) { ULL ret=0; for(int i=1;i<=s.size();i++) { ret=ret*P+s[i-1]; } return ret; } int main() { cin>>n; for(int i=1;i<=n;i++) { string s; cin>>s; ULL x=get_hash(s); a[i]=x; } int ret=1; sort(a+1,a+1+n); for(int i=2;i<=n;i++) { if(a[i]!=a[i-1]) ret++; } cout<<ret<<endl; return 0; }