fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Node
  6. {
  7. public:
  8.    //登録する文字列
  9.    string letters;
  10.    //枝
  11.    vector<Node*> children;
  12.    //完了文字列
  13.    bool terminated;
  14.    //コンストラクタ
  15.    Node(void)
  16.    {
  17.         this->letters = "";
  18.         this->children.clear();
  19.         this->terminated = false;
  20.    }
  21.    //コンストラクタ
  22.    Node(string letters,vector <Node*>& children,bool terminated)
  23.    {
  24.         this->letters = letters;
  25.         this->children = children;
  26.         this->terminated = terminated;
  27.    }
  28.    //コンストラクタ
  29.    Node(string letters)
  30.    {
  31.         this->letters = letters;
  32.         this->children.clear();
  33.         this->terminated = true;
  34.    }
  35.    //一覧
  36.    void dump(string word)
  37.    {
  38.         string tmp = word+letters;
  39.         if( terminated ){
  40.             std::cout << tmp << "\n";
  41.         }
  42.         if( children.size() > 0 ){
  43.             for( size_t i = 0 ; i < children.size() ; i++ ){
  44.                 Node* n = children[i];
  45.                 n->dump(tmp);
  46.             }
  47.         }
  48.         return;
  49.    }
  50.    //文字が格納されているか？
  51.    bool contains(string word){
  52.         int rest = word.length();
  53.         // 自ノードの文字列のほうが長ければ比較失敗。
  54.         int n = letters.length();
  55.         if( n > rest ){
  56.             return false;
  57.         }
  58.         for( int i = 0 ; i < n ; i++ ){
  59.             if( letters[i] != word[i] ){
  60.                 return false;
  61.             }
  62.         }
  63.         // 文字列が同じであれば、終端かどうかを返す。
  64.         if( n == rest ){
  65.             return terminated;
  66.         }
  67.         word = word.substr(n);
  68.         if( children.size() > 0 ){
  69.             char c = word[0];
  70.             for( size_t i = 0 ; i < children.size() ; i++ ){
  71.                 Node n = *children[i];
  72.                 if( n.letters[0] == c ){
  73.                     return n.contains(word);
  74.                 }
  75.             }
  76.         }
  77.         return false;
  78.    }
  79.    //文字を枝登録
  80.    void insertChild(string letters)
  81.    {
  82.        int n = min(letters.length(), this->letters.length());
  83.        int i = 0;
  84.        //合致する文字数を計算
  85.        while(i < n && (letters[i] == this->letters[i])){
  86.            i++;
  87.        }
  88.        //少なくとも片方を包含
  89.        if(i == n){
  90.            //全部合致。terminateフラグたてて終わり
  91.            if(letters.length() == this->letters.length()){
  92.                terminated = true; // (a)
  93.                return;
  94.            }
  95.            //登録する文字の方が少ない
  96.            if(letters.length() < this->letters.length()){
  97.                //残りの文字についてノードを作成
  98.                Node* node = new Node(this->letters.substr(letters.length()),this->children, this->terminated);
  99.                //このノードは指定文字列
  100.                this->letters = letters;
  101.                //1個のベクタ作成
  102.                this->children.clear();
  103.                //node格納
  104.                this->children.push_back(node);
  105.                this->terminated = true;
  106.                return;
  107.            }
  108.            //登録する文字の方が長い
  109.            letters = letters.substr(i);
  110.            int index = 0;
  111.            for( size_t i = 0 ; i < children.size() ; i++ ){
  112.                Node* child = children[i];
  113.                int c = letters[0] - child->letters[0];
  114.                if(c < 0) break;
  115.                if(c == 0){
  116.                    child->insertChild(letters); // (c)
  117.                    return;
  118.                }
  119.                index++;
  120.            }
  121.            //
  122.            this->children.insert(children.begin()+index, new Node(letters)); // (d)
  123.            return;
  124.        }
  125.        //包含しあわない場合
  126.        //合致するところで切り分け
  127.        string newLetter1 = this->letters.substr(0, i); // (e)
  128.        string newLetter2 = this->letters.substr(i);
  129.        string newLetter3 = letters.substr(i);
  130.        if(newLetter2[0] < newLetter3[0]){
  131.            children.push_back(new Node(newLetter2, this->children, this->terminated));
  132.            children.push_back(new Node(newLetter3));
  133.        }else{
  134.            children.push_back(new Node(newLetter3));
  135.            children.push_back(new Node(newLetter2, this->children, this->terminated));
  136.        }
  137.        this->letters = newLetter1;
  138.        this->terminated = false;
  139.        this->children = children;
  140.     }       
  141. };
  142. //---------------------------------------------------------------------------
  143.  
  144. //テーブルクラステスト
  145. int main()
  146. {
  147.         Node* test= new Node();
  148.         test->insertChild("test");
  149.         test->insertChild("test2");
  150.         test->insertChild("abc");
  151.         test->dump("");
  152.         int found = test->contains("abc");
  153.         delete test;
  154. }
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
abc
test
test2
https://ideone.com/MO8DxW
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!