#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#define N 256

using namespace std;

struct TreeNode {
	bool isEnd;
	struct TreeNode *next[N];
};

class Trie {
public:
	Trie();
	void InsertNode(string query);
	void FindStr(string query, vector<string> &result);
	void FindStrCore(TreeNode *root,string query, vector<string> &result);
	void clear();
	void DeleteNode(TreeNode *root);
	int IsError(string query);
	void CorrectSpell(string query, vector<string> &res);
	void ErrorCheck(TreeNode *root, string query);
	~Trie();
private:
	TreeNode *root;
};

Trie::Trie() {
	root = new TreeNode();
	root->isEnd = false;
	for (int i = 0;i < N; i ++) {
		root->next[i] = NULL;
	}
}

void Trie::FindStrCore(TreeNode *root, string query, vector<string> &result) {
	TreeNode *p = root;
	if (root == NULL)
		return;
	if (root->isEnd)
		result.push_back(query);
	for (int i = 0;i < N; i ++) {
		if (root->next[i] != NULL) {
			char c = (char)i;
			FindStrCore(root->next[i], query+c, result);
		}
	}
}

void Trie::FindStr(string src, vector<string> &result) {
	int cur = 0;
	TreeNode *p = this->root;
	unsigned char index = (unsigned char) src[cur];

	while (cur < src.size() && p->next[index]) {
		p = p->next[index];
		++cur;
		index = (unsigned char) src[cur];
	}
	if (cur != src.size() || p == NULL) {
		return;
	}
	FindStrCore(p, src, result);
}

int Trie::IsError(string query) {
	TreeNode *p = this->root;
	if (p == NULL)
		return 0;
	int cur = 0;
	unsigned char index = (unsigned char) query[cur];
	while(cur < query.size() && p->next[index]) {
		p = p->next[index];
		++ cur;
		index = (unsigned char) query[cur];
	}
	if (!p->isEnd)
		return cur;

	return 0;
}

void Trie::CorrectSpell(string query, vector<string> &res) {
	int index = IsError(query);
	if (index) {
		string sub = query.substr(0, index);
		FindStr(sub, res);
	}
}

void Trie::InsertNode(string str) {
	TreeNode *p = this->root;
	for (int i = 0; i < str.size(); i ++) {
		unsigned char index = (unsigned char)str[i];
		if (p->next[index] == NULL)
			p->next[index] = new TreeNode();

		p = p->next[index];
	}
	p->isEnd = true;
}

void Trie::DeleteNode(TreeNode *root) {
	for (int i = 0; i < N; i ++) {
		if (root->next[i] != NULL) {
			DeleteNode(root->next[i]);
		}
	}
	free(root);
}

Trie::~Trie() {
	DeleteNode(root);
}

int main(int argc, char *argv[])
{
	Trie *p = new Trie();
	p->InsertNode("hello world");
	p->InsertNode("hello baby");
	p->InsertNode("hello emm..");
	p->InsertNode("hello");
	p->InsertNode("你好啊");
	p->InsertNode("你真好");
	p->InsertNode("你好坏");

	string query;
	cout << "Please input query" << endl;
	cin >> query;

	vector<string> result;
	//p->FindStr(query, result);

	p->CorrectSpell(query, result);

	vector<string>::iterator it;
	if (result.size() > 0)
		cout << "You may want input:" << endl;
	else
		cout << "You input is correct" << endl;
	for(it = result.begin(); it != result.end(); ++ it){
		cout << *it << endl;
	}
	return 0;
}