fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <stdlib.h>
  5. #include <string>
  6. #include <vector>
  7. using namespace std;
  8. class Node{
  9. public:
  10.    //登録する文字列
  11.    vector<string> data;
  12.    //完了フラグ
  13.    vector<int> terminated;
  14.    //枝
  15.    vector<int> children;
  16.    vector<int> brothers;
  17.    vector<int> parents;
  18.    vector<int> index;
  19.    //コンストラクタ
  20.    Node(void);
  21.    void print(int ptr=0);
  22.    void dump(int ptr=0);
  23.    int  contains(string letters, int parent = 0);
  24.    int  addNode(string letters,int child,int brother,int parent,int terminate);
  25.    void insertChild(string letters,int parent=0);
  26.    void setParent(int bros);
  27.    string sprint(int ptr);
  28.  
  29. };
  30.  
  31. //コンストラクタ
  32. Node::Node(void)
  33. {
  34.     data.push_back("");
  35.     children.push_back(-1);
  36.     brothers.push_back(-1);
  37.     parents.push_back(-1);
  38.     terminated.push_back(0);
  39. }
  40. //Terminatedで示されるノードの文字列表示
  41. void Node::print(int ptr)
  42. {
  43.     if( terminated[ptr] ){
  44.         string word = data[ptr];
  45.         while( parents[ptr]>=0 ){
  46.             ptr = parents[ptr];
  47.             word = data[ptr] + word;
  48.         }
  49.         printf( "%s,",word.c_str());
  50.     }
  51. }
  52. //Terminatedで示されるノードの文字列取得
  53. string Node::sprint(int ptr)
  54. {
  55.     if( terminated[ptr] ){
  56.         string word = data[ptr];
  57.         while( parents[ptr]>=0 ){
  58.             ptr = parents[ptr];
  59.             word = data[ptr] + word;
  60.         }
  61.         return word;
  62.     }
  63.     return "";
  64. }
  65. //一覧
  66. void Node::dump(int ptr)
  67. {
  68.     static int cnt=0;
  69.     //無限ループ防ぐ。デバッグ用
  70.     if( cnt++ > 100 ){
  71.         return;
  72.     }
  73.     if( terminated[ptr] ){
  74.         print(ptr);
  75.     }
  76.     if( children[ptr] >= 0 ){
  77.         dump( children[ptr] );
  78.     }
  79.     if( brothers[ptr] >= 0 ){
  80.         dump( brothers[ptr] );
  81.     }
  82.     return;
  83. }
  84. //文字が格納されているか？
  85. int Node::contains(string letters, int parent)
  86. {
  87.     //子供を検索
  88.     int bros = children[parent];
  89.     while( bros >= 0 ){
  90.         //１文字目を比較
  91.         if ( letters[0]-data[bros][0] == 0 ){
  92.             //長さ比較
  93.             int n = min(letters.length(), data[bros].length());
  94.             //合致数計算
  95.             int i = 0;
  96.             while(i < n && (letters[i] == data[bros][i])) i++;
  97.             if( i == n ){
  98.                 //完全一致の場合
  99.                 if( letters.length() == data[bros].length() ){
  100.                     return terminated[bros];
  101.                 //登録文字の方が長いので子ノードに再帰的に登録
  102.                 }else{
  103.                     //登録する文字の方が長いので必ず子供が出来る
  104.                     return contains( letters.substr(i),bros);
  105.                 }
  106.             }
  107.         }
  108.         bros = brothers[bros];
  109.     }
  110.     return -1;
  111. }
  112. int Node::addNode(string letters,int child,int brother,int parent,int terminate)
  113. {
  114.     int ptr = data.size();
  115.     data.push_back(letters);
  116.     parents.push_back(parent);
  117.     children.push_back(child);
  118.     brothers.push_back(brother);
  119.     terminated.push_back(terminate);
  120.     if( terminate ){
  121.         index.push_back(ptr);
  122.     }
  123.     //登録場所を返す
  124.     return ptr;
  125. }
  126.  
  127. //文字を枝登録。親となるノードを返す
  128. void Node::insertChild(string letters, int parent)
  129. {
  130.     int child;
  131.     int previous;
  132.     int bros;
  133.     int ptr;
  134.  
  135.     //子供に要素を挿入
  136.     bros = children[parent];
  137.     previous = bros;
  138.     while( bros >= 0 ){
  139.         //１文字目を比較
  140.         int c = letters[0]-data[bros][0];
  141.         //先頭または途中挿入
  142.         if( c < 0 ){
  143.             //先頭
  144.             if( bros == children[parent] ){
  145.                 //新規子無、先頭指定の兄弟、親は引数
  146.                 ptr = addNode(letters,-1,bros,parent,1);
  147.                 //親ノードの子順番変更。ここは変更可能
  148.                 children[parent] = ptr;
  149.                 return;
  150.             //途中挿入
  151.             }else{
  152.                 //新規子無、先頭指定の兄弟、親は引数
  153.                 ptr = addNode(letters,-1,bros,parent,1);
  154.                 //先頭でないので兄弟を変更
  155.                 brothers[previous] = ptr;
  156.                 return;
  157.             }
  158.         }else if ( c == 0 ){
  159.             //長さ比較
  160.             int n = min(letters.length(), data[bros].length());
  161.             //合致数計算
  162.             int i = 0;
  163.             while(i < n && (letters[i] == data[bros][i])) i++;
  164.             if( i == n ){
  165.                 //一致
  166.                 //より短い一致の挿入
  167.                 //より長い文字の挿入
  168.  
  169.                 //完全一致の場合
  170.                 if( letters.length() == data[bros].length() ){
  171.                     terminated[bros] = 1;
  172.                     index.push_back(bros);
  173.                     return;
  174.                 //登録文字の方が短い
  175.                 }else if( letters.length() < data[bros].length()){
  176.                     int c1    =  addNode(letters,bros,brothers[bros],parents[bros],1);
  177.                     //子供、兄弟の情報は保持
  178.                     data[bros] = data[bros].substr(i);
  179.                     if( bros == previous ){
  180.                         children[parents[bros]] = c1;
  181.                     }else{
  182.                         brothers[previous] = c1;
  183.                     }
  184.                     parents[bros]  = c1;     
  185.                     brothers[bros] = -1;
  186.                     return;
  187.                 //登録文字の方が長いので子ノードに再帰的に登録
  188.                 }else{
  189.                     //登録する文字の方が長いので必ず子供が出来る
  190.                     letters = letters.substr(i);
  191.                     insertChild( letters,bros);
  192.                     //parents[children[bros]] = bros;
  193.                     return;
  194.                 }
  195.             }else{
  196.                 //先頭だけ合致。２つの子ノードが出来る
  197.                 string newLetter1 = data[bros].substr(0, i);
  198.                 string newLetter2 = data[bros].substr(i);
  199.                 string newLetter3 = letters.substr(i);
  200.                 data[bros] = newLetter2;
  201.                 if(newLetter2[0] < newLetter3[0]){
  202.                     int c1                  = addNode(newLetter1,bros,-1,parents[bros],0);
  203.                     brothers[bros]          = addNode(newLetter3,-1,-1,-1,1);
  204.                     //先頭の場合は親をletter1に設定
  205.                     if( previous == bros ){
  206.                         children[parents[bros]] = c1;
  207.                     //先頭でなければ兄弟を設定
  208.                     }else{
  209.                         brothers[previous]      = c1;
  210.                     }
  211.                     //分割した文字の親はletter1
  212.                     parents[bros]           = c1;
  213.                     //letter3の親もletter1
  214.                     parents[brothers[bros]] = c1;
  215.                 }else{
  216.                     int c1                  = addNode(newLetter1,-1,brothers[bros],parents[bros],0);
  217.                     int c2                  = addNode(newLetter3,-1,bros,c1,1);
  218.                     //先頭の場合は親を設定
  219.                     if( previous == bros ){
  220.                         children[parents[bros]] = c1;
  221.                     //先頭でなければ兄弟を設定
  222.                     }else{
  223.                         brothers[previous]      = c1;
  224.                     }
  225.                     brothers[bros]          = -1;
  226.                     parents[bros]           = c1;
  227.                     children[parents[bros]] = c2;
  228.                 }
  229.                 //children[parents[parents[bros]]] = parents[bros];
  230.                 return;
  231.             }
  232.         }
  233.         previous = bros;
  234.         bros = brothers[bros];
  235.         if( bros < 0 ){
  236.             //末尾に挿入
  237.             ptr = addNode(letters,-1,-1,parent,1);
  238.             brothers[previous] = ptr;
  239.             return;
  240.         }
  241.     }
  242.     //ループしなかった子供なし
  243.     children[parent] =  addNode(letters,-1,-1,parent,1);
  244.     return;
  245. }
  246. //---------------------------------------------------------------------------
  247. string makeword()
  248. {
  249.     char data[]="abcdefghijklmnopqrstuvwxyz";
  250.     int len=strlen(data);
  251.     string word;
  252.     int tlen=rand() % 15+1;
  253.     for( int i = 0 ; i < tlen ; i++ ){
  254.         word = word + data[rand() % len];
  255.     }
  256.     return word;
  257. }
  258. void dotest()
  259. {
  260.         Node* test= new Node();
  261.         vector<string> tests;
  262.         //値作成
  263.         for( int i = 0 ; i < 10 ; i++ ){
  264.             while(true){
  265.                 string word = makeword();
  266.                 int flg = 0;
  267.                 for( int j = 0 ; j<i-1 ; j++ ){
  268.                     if( word == tests[j] ){
  269.                         flg = 1;
  270.                         break;
  271.                     }
  272.                 }
  273.                 if( flg == 0 ){
  274.                      tests.push_back(word);
  275.                     break;
  276.                 }
  277.             }
  278.         }
  279.         //insertしていく
  280.         for( int i = 0 ; i < tests.size() ; i++ ){
  281.             test->insertChild(tests[i].c_str());
  282.             if( i+1 != test->index.size() ){
  283.                 getchar();
  284.             }
  285.         }
  286.         //結果表示
  287.         for( int i = 0 ; i < test->index.size() ; i++ ){
  288.             printf( "%s\n%s\n", tests[i].c_str(), test->sprint(test->index[i]).c_str());
  289.             if( tests[i] != test->sprint(test->index[i]) ){
  290.                 getchar();
  291.             }
  292.         }
  293.         //test->dump();
  294.         delete test;
  295. }
  296. int main() {
  297. 	// your code goes here
  298.     dotest();
  299. 	return 0;
  300. }
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
wlrbbmqbhcdarz
wlrbbmqbhcdarz
wk
wk
yhiddqsc
yhiddqsc
xrjmowfrxsjybl
xrjmowfrxsjybl
befsarc
befsarc
ynecdyggx
ynecdyggx
p
p
lorellnmpapqfwk
lorellnmpapqfwk
opkm
opkm
oqhnwnkue
oqhnwnkue
https://ideone.com/IXbDVB
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!