理论知识与功能
定义
Trie(字典树),用于实现字符串的快速检索。其每个节点都含有若干个字符指针。
例如我在字典树里插入"abc","ac",那么就会生成一个这样丑陋的东西。
好吧是我的图画的丑陋
初始化
一棵空的Trie仅包含一个根节点,那么他的指针自然也指向空。
注:因为Trie运用在检索字符串,所以此处指针指代字符指针。
插入
对于需要插入的一个字符串S而言,我们令指针P指向根节点。然后依次扫描P中的每个字符c
1.若P的c字符指针指向空(即没有这个节点),则新建一个节点Q,令P的c字符指针指向Q,然后令P=Q。
2.若指向一个已存在的节点,直接让P=Q。
当S字符扫描完毕时,在当前节点P上标记他是一个字符串的末尾。
检索
对于需要检索的一个字符串S而言,我们令指针P指向根节点,然后依次扫描S中的每个字符c
1.若P的c指针指向空,则S没有被插入过Trie,返回False
2.若指向存在的节点,则P=Q
当S扫描完毕时,检查P是否被标记为一个字符的末尾。如果没有,就是False。否则为True
代码实现
int trie[Size][26],tot=1; void insert(char* str){ int len=strlen(str),p=1; for(int k=0;k<len;k++){ int ch=str[k]-'a'; if(trie[p][ch]==0){ trie[p][ch]=++tot; } p=trie[p][ch]; } end[p]=true; } bool search(char* str){ int len=strlen(str),p=1; for(int k=0;k<len;k++){ p=trie[p][str[k]-'a']; if(p==0){ return false; } } return end[p]; }
题中的Show Time
前缀统计 CH1601
当笔者想去整理的时候…
唉。
好文章 2015模拟题
这道题Trie不是正解,但是可以拿到一定分数。
#include<iostream> #include<cstring> using namespace std; const int Size=200100; int trie[Size][26]; bool end[Size]; char S[Size]; int tot; int ans; int n,m; bool Search(int pos){ //int len=strlen(str),p=1; int len=m,p=1; for(int k=0;k<len;k++){ p=trie[p][S[k+pos]-'a']; if(p==0){ return false; } } return end[p]; } void Insert(int pos){//char *str //int len=strlen(str),p=1; if(Search(pos)){ //cout<<"重复"<<endl; return; } int len=m,p=1; for(int k=0;k<len;k++){ int ch=S[pos+k]-'a'; if(trie[p][ch]==0){ trie[p][ch]=++tot; //cout<<"p "<<p<<endl; } p=trie[p][ch]; } end[p]=true; ans++; } int main(){ //abc bca cab aba bac acb cba //string s; //freopen("B.in","r",stdin); //freopen("B.out","w",stdout); cin>>n>>m>>S; for(int i=0;i<=n-m;i++){ //cout<<"运行"<<endl; Insert(i); } cout<<ans; }
50分解法。但由于用到了Trie,所以粘了过来。据题解所述,Trie最高能拿70分,但抱歉我没有看懂。