#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
using namespace std;
class Node{
public:
//登録する文字列
vector<string> data;
//完了フラグ
vector<int> terminated;
//枝
vector<int> children;
vector<int> brothers;
vector<int> parents;
vector<int> index;
//コンストラクタ
Node(void);
void print(int ptr=0);
void dump(int ptr=0);
int contains(string letters, int parent = 0);
int addNode(string letters,int child,int brother,int parent,int terminate);
void insertChild(string letters,int parent=0);
void setParent(int bros);
string sprint(int ptr);
};
//コンストラクタ
Node::Node(void)
{
data.push_back("");
children.push_back(-1);
brothers.push_back(-1);
parents.push_back(-1);
terminated.push_back(0);
}
//Terminatedで示されるノードの文字列表示
void Node::print(int ptr)
{
if( terminated[ptr] ){
string word = data[ptr];
while( parents[ptr]>=0 ){
ptr = parents[ptr];
word = data[ptr] + word;
}
printf( "%s,",word.c_str());
}
}
//Terminatedで示されるノードの文字列取得
string Node::sprint(int ptr)
{
if( terminated[ptr] ){
string word = data[ptr];
while( parents[ptr]>=0 ){
ptr = parents[ptr];
word = data[ptr] + word;
}
return word;
}
return "";
}
//一覧
void Node::dump(int ptr)
{
static int cnt=0;
//無限ループ防ぐ。デバッグ用
if( cnt++ > 100 ){
return;
}
if( terminated[ptr] ){
print(ptr);
}
if( children[ptr] >= 0 ){
dump( children[ptr] );
}
if( brothers[ptr] >= 0 ){
dump( brothers[ptr] );
}
return;
}
//文字が格納されているか?
int Node::contains(string letters, int parent)
{
//子供を検索
int bros = children[parent];
while( bros >= 0 ){
//1文字目を比較
if ( letters[0]-data[bros][0] == 0 ){
//長さ比較
int n = min(letters.length(), data[bros].length());
//合致数計算
int i = 0;
while(i < n && (letters[i] == data[bros][i])) i++;
if( i == n ){
//完全一致の場合
if( letters.length() == data[bros].length() ){
return terminated[bros];
//登録文字の方が長いので子ノードに再帰的に登録
}else{
//登録する文字の方が長いので必ず子供が出来る
return contains( letters.substr(i),bros);
}
}
}
bros = brothers[bros];
}
return -1;
}
int Node::addNode(string letters,int child,int brother,int parent,int terminate)
{
int ptr = data.size();
data.push_back(letters);
parents.push_back(parent);
children.push_back(child);
brothers.push_back(brother);
terminated.push_back(terminate);
if( terminate ){
index.push_back(ptr);
}
//登録場所を返す
return ptr;
}
//文字を枝登録。親となるノードを返す
void Node::insertChild(string letters, int parent)
{
int child;
int previous;
int bros;
int ptr;
//子供に要素を挿入
bros = children[parent];
previous = bros;
while( bros >= 0 ){
//1文字目を比較
int c = letters[0]-data[bros][0];
//先頭または途中挿入
if( c < 0 ){
//先頭
if( bros == children[parent] ){
//新規子無、先頭指定の兄弟、親は引数
ptr = addNode(letters,-1,bros,parent,1);
//親ノードの子順番変更。ここは変更可能
children[parent] = ptr;
return;
//途中挿入
}else{
//新規子無、先頭指定の兄弟、親は引数
ptr = addNode(letters,-1,bros,parent,1);
//先頭でないので兄弟を変更
brothers[previous] = ptr;
return;
}
}else if ( c == 0 ){
//長さ比較
int n = min(letters.length(), data[bros].length());
//合致数計算
int i = 0;
while(i < n && (letters[i] == data[bros][i])) i++;
if( i == n ){
//一致
//より短い一致の挿入
//より長い文字の挿入
//完全一致の場合
if( letters.length() == data[bros].length() ){
terminated[bros] = 1;
index.push_back(bros);
return;
//登録文字の方が短い
}else if( letters.length() < data[bros].length()){
int c1 = addNode(letters,bros,brothers[bros],parents[bros],1);
//子供、兄弟の情報は保持
data[bros] = data[bros].substr(i);
if( bros == previous ){
children[parents[bros]] = c1;
}else{
brothers[previous] = c1;
}
parents[bros] = c1;
brothers[bros] = -1;
return;
//登録文字の方が長いので子ノードに再帰的に登録
}else{
//登録する文字の方が長いので必ず子供が出来る
letters = letters.substr(i);
insertChild( letters,bros);
//parents[children[bros]] = bros;
return;
}
}else{
//先頭だけ合致。2つの子ノードが出来る
string newLetter1 = data[bros].substr(0, i);
string newLetter2 = data[bros].substr(i);
string newLetter3 = letters.substr(i);
data[bros] = newLetter2;
if(newLetter2[0] < newLetter3[0]){
int c1 = addNode(newLetter1,bros,-1,parents[bros],0);
brothers[bros] = addNode(newLetter3,-1,-1,-1,1);
//先頭の場合は親をletter1に設定
if( previous == bros ){
children[parents[bros]] = c1;
//先頭でなければ兄弟を設定
}else{
brothers[previous] = c1;
}
//分割した文字の親はletter1
parents[bros] = c1;
//letter3の親もletter1
parents[brothers[bros]] = c1;
}else{
int c1 = addNode(newLetter1,-1,brothers[bros],parents[bros],0);
int c2 = addNode(newLetter3,-1,bros,c1,1);
//先頭の場合は親を設定
if( previous == bros ){
children[parents[bros]] = c1;
//先頭でなければ兄弟を設定
}else{
brothers[previous] = c1;
}
brothers[bros] = -1;
parents[bros] = c1;
children[parents[bros]] = c2;
}
//children[parents[parents[bros]]] = parents[bros];
return;
}
}
previous = bros;
bros = brothers[bros];
if( bros < 0 ){
//末尾に挿入
ptr = addNode(letters,-1,-1,parent,1);
brothers[previous] = ptr;
return;
}
}
//ループしなかった子供なし
children[parent] = addNode(letters,-1,-1,parent,1);
return;
}
//---------------------------------------------------------------------------
string makeword()
{
char data[]="abcdefghijklmnopqrstuvwxyz";
int len=strlen(data);
string word;
int tlen=rand() % 15+1;
for( int i = 0 ; i < tlen ; i++ ){
word = word + data[rand() % len];
}
return word;
}
void dotest()
{
Node* test= new Node();
vector<string> tests;
//値作成
for( int i = 0 ; i < 10 ; i++ ){
while(true){
string word = makeword();
int flg = 0;
for( int j = 0 ; j<i-1 ; j++ ){
if( word == tests[j] ){
flg = 1;
break;
}
}
if( flg == 0 ){
tests.push_back(word);
break;
}
}
}
//insertしていく
for( int i = 0 ; i < tests.size() ; i++ ){
test->insertChild(tests[i].c_str());
if( i+1 != test->index.size() ){
getchar();
}
}
//結果表示
for( int i = 0 ; i < test->index.size() ; i++ ){
printf( "%s\n%s\n", tests[i].c_str(), test->sprint(test->index[i]).c_str());
if( tests[i] != test->sprint(test->index[i]) ){
getchar();
}
}
//test->dump();
delete test;
}
int main() {
// your code goes here
dotest();
return 0;
}