Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
使用trie进行补全和检查错误。
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment