|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> using namespace std; struct trieNode{ trieNode* child[30]; int count; bool exist; trieNode(){ memset(child, NULL, sizeof(child)); count = 0; exist = false; } } trie,*currNode; int main(){ string str; bool status = true; while (getline(cin,str)) { if (str.size() == 0) { status = false; continue; } if (status) { currNode = ≜ for (int i = 0; i < str.size(); i++) { if((*currNode).child[str[i]-'a'] == NULL){ (*currNode).child[str[i]-'a'] = new trieNode; }else{ (*currNode).child[str[i]-'a']->count++; if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true; } currNode = (*currNode).child[str[i]-'a']; } }else{ currNode = ≜ bool flag = false; for (int i = 0; i < str.size(); i++) { if((*currNode).child[str[i]-'a'] == NULL){ break; }else{ if (i == str.size()-1) { cout << (*currNode).child[str[i]-'a']->count+1<< endl; flag = true; } } currNode = (*currNode).child[str[i]-'a']; } if (!flag) { cout << 0 << endl; } } } } |
涨姿势了，new开辟的内存空间中变量是没有被初始化的，要自己写一个初始化的constructor才可以，否则就是RERERE。。。
然后Trie的实现方法基本就是这样，指针写法还是比较好弄的，但是以后还要考虑垃圾回收的问题。
