题解 P3370 【【模板】字符串哈希】
fly20040720
2018-04-07 18:49:32
正常来讲哈希的查找/修改是O(1)的(不得不说很优美,也很优秀),而set、map、unordered_map之类的东西都是O(logn)的,而且据说字符串用>、<、和=的比较都是O(lenth)的。但是应为这题数据比较水,就过了。
## # **先来看一下手写的排序树(蒟蒻不会写平衡树):**#
字符串如果用> 、<、=比较大小可能比较玄学,但这不重要,只要保证规则不改变就行了。至于排序树,就把正常的树删掉一堆功能,再把int改成string就行了。
```cpp
#include<iostream>
using namespace std;
int n,size;//计算数量
string s;
struct node
{
string v;
node *lc,*rc;//只会指针版的(也是方便以后平衡树的旋转操作)
node(string v="",node *l=NULL,node *r=NULL)
{
this->v=v;
this->lc=l;
this->rc=r;
}//初始化(虽然并没有什么用)
}*root=new node;//申请内存
void insert(string val,node *cur)//插入(懒得写成员函数)
{
if(cur->v>val)
if(cur->lc==NULL)
{
node *c=new node;
cur->lc=c;
c->v=val;
}
else
insert(val,cur->lc);
else
{
if(cur->rc==NULL)
{
node *c=new node;
cur->rc=c;
c->v=val;
}
else
insert(val,cur->rc);
}
}//标准排序树,没什么好说的
bool find(string v,node *cur)//查找
{
if(cur->v==v)
return true;
else if(cur->v>v)
if(cur->lc==NULL)
return false;
else
return find(v,cur->lc);
else
if(cur->rc==NULL)
return false;
else
return find(v,cur->rc);
}
int main()
{
cin>>n;
cin>>s;
insert(s,root);
size++;//第一个肯定不会重合
for(int i=1;i<n;i++)
{
cin>>s;
if(!find(s,root))
{
size++;
insert(s,root);
}
}
cout<<size;//经人工亲测,不写return 0;不会死人
}
```
## 再看STL的set/map/unordered_map(其实基本一样,这里只写一种)
```cpp
#include<iostream>
#include<unordered_map>//c++11新特性
using namespace std;
int n;
string s;
unordered_map<string,bool>m;//申请
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s;
m[s]=1;//等于几不重要,有就行
}
cout<<m.size();//懒
}
```
[博客](https://www.luogu.org/blog/mayinfei/solution-p3370)