最近学习了一下关于Trie的一些姿势，感觉很实用。
终于不用每次看到字符串判重等操作就只想到hash了
关于Trie的定义，来自百度百科
在计算机科学中，Trie，又称前缀树或字典树，是一种有序树状的数据结构，用于保存关联数组，其中的键通常是字符串。
说的有点高级，我们不要管它，可以看这样一张图：
这棵Trie中的单词共有:his,he,her,me,your
就是从根节点一直到某个有end（结尾）标记的点
可以发现，Tire其实就是把一些字符串的公用前缀字符存储了下来
Tire的实现更是简单：
-
建立一棵Trie，初始时只有一个空的根节点（编号为0）
-
每当插入或删除时，如果当前字符在之前的操作中已经建立，然后直接利用即可，否则新建立一个节点并让上一个节点连上它
-
当一个字符串结束时，给该节点做个记号，同时也可存储些其它的信息
具体的实现方法也有两种：邻接表和邻接矩阵
在Trie中，显然用邻接矩阵是很快的，但空间的开销可能较大，如果题目说明范围，那么空间允许的情况下可以使用
邻接表还是一样，比较省空间（毕竟要多少开多少）
这里用一道板子题来理解一下：
邻接矩阵CODE
#include<iostream>
#include<string>
using namespace std;
const int N=50005;
struct node
{
bool end;
int next[30];
}trie[N<<4];
string s;
int n,ans,cnt;
inline bool find(string s)
{
int now=0,len=s.size();
for (register int i=0;i<len;++i)
{
if (trie[now].next[s[i]-'a'+1]) now=trie[now].next[s[i]-'a'+1]; else return 0;
if (i==len-1) return trie[now].end;
}
}
inline void insert(string s)
{
int now=0,len=s.size();
for (register int i=0;i<len;++i)
{
if (trie[now].next[s[i]-'a'+1]) now=trie[now].next[s[i]-'a'+1]; else trie[now].next[s[i]-'a'+1]=++cnt,now=cnt;
if (i==len-1) trie[now].end=1;
}
}
int main()
{
register int i;
for (cin>>n,i=1;i<=n;++i)
{
cin>>s;
string rs(s.rbegin(),s.rend());
if (find(rs)) ++ans;
insert(s);
}
cout<<ans;
return 0;
}
邻接表CODE
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int N=50005;
struct node
{
bool end;
char ch;
}trie[N<<4];
struct edge
{
int to,next;
}link[N<<4];
string s;
int head[N<<4],n,ans,cnt;
inline void add(int x,int y,char z)
{
link[y].to=y; trie[y].ch=z; link[y].next=head[x]; head[x]=y;
}
inline bool find(string s)
{
int now=0,len=s.size();
for (register int i=0;i<len;++i)
{
bool flag=0;
for (register int j=head[now];j!=-1;j=link[j].next)
if (trie[link[j].to].ch==s[i]) { flag=1; now=link[j].to; break; }
if (!flag) return 0;
if (i==len-1) return trie[now].end;
}
}
inline void insert(string s)
{
int now=0,len=s.size();
for (register int i=0;i<len;++i)
{
bool flag=0;
for (register int j=head[now];j!=-1;j=link[j].next)
if (trie[link[j].to].ch==s[i]) { flag=1; now=link[j].to; break; }
if (!flag) add(now,++cnt,s[i]),now=cnt;
if (i==len-1) trie[now].end=1;
}
}
int main()
{
register int i;
memset(link,-1,sizeof(link));
memset(head,-1,sizeof(head));
for (cin>>n,i=1;i<=n;++i)
{
cin>>s;
string rs(s.rbegin(),s.rend());
if (find(rs)) ++ans;
insert(s);
}
cout<<ans;
return 0;
}