题解 P3370 【【模板】字符串哈希】

正常来讲哈希的查找/修改是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)