洛谷P3370 【模板】字符串哈希(c嘎嘎）

题目链接：P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教诲新生态
题目难度：普及

解题思路：利用哈希算法，将每一个字符串映射到一个值域较小、可以方便比较的数，然后将哈希值存入到set（不能有重复元素），最后输出set的大小。

代码部分：

1. #include<bits/stdc++.h>//万能头文件
2. using namespace std;
3. typedef unsigned long long ULL;
4. const int N = 100010,P = 131;
6. int n;
7. ULL h[N];
8. char s[N];
9. set<ULL>st;
11. int get_hash(char s[])//哈希函数
12. {
13.         h[0] = 0;
14.         int len = strlen(s);
15.         for(int i=0; i<len; i++)
16.         {
17.                 h[i + 1] = h[i] * P + s[i];
18.         }
19.         return h[len];
20. }
21. int main()
22. {
23.     ios::sync_with_stdio(0);
24.     cin.tie(0), cout.tie(0);
25.    
26.     cin >> n;
27.    
28.         while(n--)//读入
29.         {
30.                 cin >> s;
31.                 st.insert(get_hash(s));//插入set中
32.         }
33.     cout<<st.size();
34.              
35.     return 0;  
36. }

复制代码