字典树的建立以及查找
1234567891011121314151617181920212223
//建立字典树 void insert(string str,int trie[][26],int *tot,bool end[]){ int len=str.size(),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; } //查找str是否在字典中出现 bool search (string str,int trie[][26],bool end[]){ int len=str.size(),p=1; for (int k=0;k<len;k++){ p=trie[p][str[k]-'a']; if (!p){ return false; } } return end[p]; }
例题:P3879 [TJOI2010] 阅读理解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
#include <iostream> using namespace std; #define N 1010 #define L 5010 void insert (string str,int trie[][30],int *tot,bool end[]){//建树 int len=str.size(),p=1,ch; for (int i=0;i<len;i++){ ch=str[i]-'a'; if (!trie[p][ch]){ trie[p][ch]=++*tot; } p=trie[p][ch]; } end[p]=true; } bool search(string str,int trie[][30],bool end[]){//查找 int len=str.size(),p=1; for (int i=0;i<len;i++){ p=trie[p][str[i]-'a']; if (!p){ return false; } } return end[p]; } int trie[N][L][30],tot; bool end1[N][L]; int main () { string str; int n,m,t; cin>>n; for(int i=1;i<=n;i++){ tot=1; cin>>t; while(t--){ cin>>str; insert(str,trie[i],&tot,end1[i]); } } cin>>m; while (m--){ cin>>str; bool flag=false; for (int i=1;i<=n;i++){ if (search(str,trie[i],end1[i])){ if (flag){ cout<<" "; } cout<<i; flag=true; } } cout<<endl; } return 0; }