P3370 【模板】字符串哈希

题目描述

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

#友情提醒:如果真的想好好练习哈希的话,请自觉,否则请右转PJ试炼场:)

输入格式

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

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

输出格式

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

输入输出样例

INPUT:
  5
abc
aaaa
abc
abcc
12345
OUTPUT:  4

可好玩一题,之前学长讲字符串的ppt里截来的,因为题目很简单所以可以用很多方法写,stl里的map和set,哈希都行,顺便学了一下字典树。

之前想了个存储字符串然后sort一遍再遍历前后比较判断总数的思路,被嫌弃了呜呜(也是,方法太笨了

以下是四个写法(再次强调字典树这题mle了○| ̄|_,

#include<bits/stdc++.h>
using namespace std;
set<string> s;
int main()
{
string s1;
int n;cin>>n;
while(n--){
cin>>s1;s.insert(s1);
}
cout<<s.size()<<endl;
}
#include<bits/stdc++.h>
const int mod=;
const int N = 1e6+;
int a[N],n,k;
using namespace std;
map<string,int>mp;
int main()
{
string s;
cin>>n;
while(n--){
cin>>s;mp[s]=;
}
cout<<mp.size()<<endl;
return ;
}
#include<bits/stdc++.h>
const int mod=;
const int N = 1e7+;
int a[N],n,k;
using namespace std;
map<string,int>mp;
int main()
{
string s;
cin>>n;
int ans=,tot=;
while(n--){
int p = ,x=;
cin>>s;
for(int i = ;i < s.size();++i){
x=x*p+s[i];
}
a[++tot]=x;
}
sort(a+,a++tot);
cout<<unique(a+,a++tot)-a-<<endl;
return ;
}
#include<bits/stdc++.h>
const int mod=;
const int N = 1e5+;
int a[N],n,k;
using namespace std;
struct node{
bool r= ;
node *next[];
};
node root;
int ans = ;char s[];
void build_trie(){
int l = strlen(s);
node *p=&root;
int flag = ;
for(int i = ;i < l;++i){
if(p->next[s[i]-'']==NULL){
p->next[s[i]-''] = new node;
}
p=p->next[s[i]-''];
}
if(p->r > )flag =;
p->r = ;
if(flag==)return ;
else ans++;
}
int main()
{
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);build_trie();
}
printf("%d\n",ans);
return ;
}

最新文章

  1. UITabBarController 更改tabbariteam上的选中图片
  2. overflow-y:auto
  3. ASP.NET下载远程图片保存到本地的方法、保存抓取远程图片
  4. magento 图片缓存是如何生成的
  5. ExpandableListView getChildView 不执行,不显示子列表
  6. centos 6.3 搭建git/gitosis/gitweb
  7. oc学习之路----scrollView的代理模式
  8. STL——前闭后开区间表示法和function call 操作符
  9. hdu1301 Jungle Roads (Prim)
  10. [Windows Phone]模仿魔兽3技能按钮SkillButton
  11. 产品经理(五岁以下儿童)myVegas Slots排名上升的秘密
  12. C# DataGridView中DataGridViewComboBoxCell列,下拉框事件的处理【完美解决】
  13. HTTP2的新特性
  14. ImCash:币圈英文术语大全
  15. leetcode — word-ladder-ii
  16. Spring+SpringMVC+Hibernate小案例(实现Spring对Hibernate的事务管理)
  17. Python Revisited Day 13 (正则表达式)
  18. shiro入门教程
  19. centos7搭建kafka集群-第二篇
  20. 用Nginx分流绕开Github反爬机制

热门文章

  1. Killer Problem (UVA 11898 )
  2. permutation 2(递推 + 思维)
  3. Java线程之wait()、notify()、notifyAll()
  4. css基础(css书写 背景设置 标签分类 css特性)
  5. zabbix监控远端主机
  6. python3中的heapq模块使用
  7. 【java测试】Junit、Mock+代码覆盖率
  8. [go]os.Open方法源码
  9. 图片加载框架之ImageLoader
  10. 整型,长整型,无符号整型等 大端和小端(Big endian and Little endian)