#include <iostream>
#include <vector>
using namespace std;
class Node
{
public:
//登録する文字列
string letters;
//枝
vector<Node*> children;
//完了文字列
bool terminated;
//コンストラクタ
Node(void)
{
this->letters = "";
this->children.clear();
this->terminated = false;
}
//コンストラクタ
Node(string letters,vector <Node*>& children,bool terminated)
{
this->letters = letters;
this->children = children;
this->terminated = terminated;
}
//コンストラクタ
Node(string letters)
{
this->letters = letters;
this->children.clear();
this->terminated = true;
}
//一覧
void dump(string word)
{
string tmp = word+letters;
if( terminated ){
std::cout << tmp << "\n";
}
if( children.size() > 0 ){
for( size_t i = 0 ; i < children.size() ; i++ ){
Node* n = children[i];
n->dump(tmp);
}
}
return;
}
//文字が格納されているか?
bool contains(string word){
int rest = word.length();
// 自ノードの文字列のほうが長ければ比較失敗。
int n = letters.length();
if( n > rest ){
return false;
}
for( int i = 0 ; i < n ; i++ ){
if( letters[i] != word[i] ){
return false;
}
}
// 文字列が同じであれば、終端かどうかを返す。
if( n == rest ){
return terminated;
}
word = word.substr(n);
if( children.size() > 0 ){
char c = word[0];
for( size_t i = 0 ; i < children.size() ; i++ ){
Node n = *children[i];
if( n.letters[0] == c ){
return n.contains(word);
}
}
}
return false;
}
//文字を枝登録
void insertChild(string letters)
{
int n = min(letters.length(), this->letters.length());
int i = 0;
//合致する文字数を計算
while(i < n && (letters[i] == this->letters[i])){
i++;
}
//少なくとも片方を包含
if(i == n){
//全部合致。terminateフラグたてて終わり
if(letters.length() == this->letters.length()){
terminated = true; // (a)
return;
}
//登録する文字の方が少ない
if(letters.length() < this->letters.length()){
//残りの文字についてノードを作成
Node* node = new Node(this->letters.substr(letters.length()),this->children, this->terminated);
//このノードは指定文字列
this->letters = letters;
//1個のベクタ作成
this->children.clear();
//node格納
this->children.push_back(node);
this->terminated = true;
return;
}
//登録する文字の方が長い
letters = letters.substr(i);
int index = 0;
for( size_t i = 0 ; i < children.size() ; i++ ){
Node* child = children[i];
int c = letters[0] - child->letters[0];
if(c < 0) break;
if(c == 0){
child->insertChild(letters); // (c)
return;
}
index++;
}
//
this->children.insert(children.begin()+index, new Node(letters)); // (d)
return;
}
//包含しあわない場合
//合致するところで切り分け
string newLetter1 = this->letters.substr(0, i); // (e)
string newLetter2 = this->letters.substr(i);
string newLetter3 = letters.substr(i);
if(newLetter2[0] < newLetter3[0]){
children.push_back(new Node(newLetter2, this->children, this->terminated));
children.push_back(new Node(newLetter3));
}else{
children.push_back(new Node(newLetter3));
children.push_back(new Node(newLetter2, this->children, this->terminated));
}
this->letters = newLetter1;
this->terminated = false;
this->children = children;
}
};
//---------------------------------------------------------------------------
//テーブルクラステスト
int main()
{
Node* test= new Node();
test->insertChild("test");
test->insertChild("test2");
test->insertChild("abc");
test->dump("");
int found = test->contains("abc");
delete test;
}