Advertisement
konchin_shih

poop

Apr 8th, 2021
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<array>
  5. #include<cstring>
  6. using namespace std;
  7. struct node{
  8.     using nptr=node*;
  9.     nptr next[128];
  10.     int cnt;
  11.     node():cnt(0){
  12.         memset(next,0,sizeof(nptr)*128);
  13.     }
  14. };
  15. using nptr=node*;
  16. struct trie{
  17.     nptr root;
  18.     void insert(const string& str){
  19.         nptr cur=root;
  20.         for(const auto& i:str){
  21.             if(!isalnum(i)) continue;
  22.             if(!cur->next[int(i)])
  23.                 cur->next[int(i)]=new node;
  24.             cur=cur->next[int(i)];
  25.         }
  26.         cur->cnt++;
  27.     }
  28.     void dfs(nptr cur){
  29.         if(!cur) return;
  30.         static string str;
  31.         if(cur->cnt)
  32.             cout<<str<<" : "<<cur->cnt<<endl;
  33.         for(int i=0;i<128;i++){
  34.             str.push_back(i);
  35.             dfs(cur->next[i]);
  36.             str.pop_back();
  37.         }
  38.     }
  39.     trie():root(new node){}
  40. };
  41. #include<fstream>
  42. int main(){
  43. //  在執行檔同資料夾放進input.txt
  44. //  執行之後輸出會在output.txt
  45.     fstream fin("input.txt",ios::in);
  46.     fstream fout("output.txt",ios::out);
  47.     cout.rdbuf(fout.rdbuf());
  48.     trie tree;
  49.     string str;
  50.     while(fin>>str)
  51.         tree.insert(str);
  52.     tree.dfs(tree.root);
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement