洛谷 P3370 【模板】字符串哈希 (set||map||哈希||字典树(mle)
2024-10-06 23:09:45
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 ;
}
最新文章
- UITabBarController 更改tabbariteam上的选中图片
- overflow-y:auto
- ASP.NET下载远程图片保存到本地的方法、保存抓取远程图片
- magento 图片缓存是如何生成的
- ExpandableListView getChildView 不执行,不显示子列表
- centos 6.3 搭建git/gitosis/gitweb
- oc学习之路----scrollView的代理模式
- STL——前闭后开区间表示法和function call 操作符
- hdu1301 Jungle Roads (Prim)
- [Windows Phone]模仿魔兽3技能按钮SkillButton
- 产品经理(五岁以下儿童)myVegas Slots排名上升的秘密
- C# DataGridView中DataGridViewComboBoxCell列,下拉框事件的处理【完美解决】
- HTTP2的新特性
- ImCash:币圈英文术语大全
- leetcode — word-ladder-ii
- Spring+SpringMVC+Hibernate小案例(实现Spring对Hibernate的事务管理)
- Python Revisited Day 13 (正则表达式)
- shiro入门教程
- centos7搭建kafka集群-第二篇
- 用Nginx分流绕开Github反爬机制
热门文章
- Killer Problem (UVA 11898 )
- permutation 2(递推 + 思维)
- Java线程之wait()、notify()、notifyAll()
- css基础(css书写 背景设置 标签分类 css特性)
- zabbix监控远端主机
- python3中的heapq模块使用
- 【java测试】Junit、Mock+代码覆盖率
- [go]os.Open方法源码
- 图片加载框架之ImageLoader
- 整型,长整型,无符号整型等 大端和小端(Big endian and Little endian)