AC字典树

main.cpp

#include <QtWidgets/QApplication>

#include "trie.h"

int main(int argc, char *argv[])
{
	QApplication a(argc, argv);
	{
		TrieNode t;
		t.Insert("你好世界");
		t.Insert("你好啊");
		t.Insert("再见");
		t.Insert("再也不见");
		t.Insert("你也好");
		t.BuildFailPointer();

		QString text("asdada你好dasdad世界vas再见dad你好啊");
		auto matches = t.Match(text);
		for (auto match : matches) {
			qDebug() << text.sliced(match.first, match.second);
		}
	}

	a.exec();
}

trie.cpp

#include "trie.h"

#include <QtWidgets>
#include <queue>

void TrieNode::Insert(const QString& s)
{
	TrieNode* cur = this;
	for (auto c : s) {
		TrieNode* next = cur->Find(c);
		if (next == nullptr) {
			TrieNode* new_node = new TrieNode;
			cur->children_[c] = new_node;
			next = new_node;
		}
		cur = next;
	}
	cur->length_ = s.length();
}

void TrieNode::BuildFailPointer()
{
	std::queue<TrieNode*> q;
	q.push(this);
	while (!q.empty()) {
		TrieNode* parent = q.front();
		q.pop();

		for (auto& kv : parent->children_) {
			QChar child_char = kv.first;
			TrieNode* child_node = kv.second;
			if (parent == this) {
				child_node->fail_ = this;
			}
			else {
				TrieNode* fail = parent->fail_;
				while (fail != nullptr) {
					TrieNode* try_find = fail->Find(child_char);
					if (try_find != nullptr) {
						child_node->fail_ = try_find;
						break;
					}
					else {
						fail = fail->fail_;
					}
				}
				if (fail == nullptr) {
					child_node->fail_ = this;
				}
			}
			q.push(child_node);
		}
	}
}

bool TrieNode::Contains(const QString& s)
{
	TrieNode* cur = this;
	for (auto c : s) {
		TrieNode* next = cur->Find(c);
		if (next == nullptr) {
			return false;
		}
		cur = next;
	}
	return cur->length_ != 0;
}

std::vector<std::pair<int, int>> TrieNode::Match(const QString& text)
{
	std::vector<std::pair<int, int>> ans;
	size_t i = 0;
	TrieNode* cur = this;
	while (i < text.length()) {
		QChar c = text[i];
		TrieNode* try_find = cur->Find(c);
		while (try_find == nullptr && cur != this) {
			cur = cur->fail_;
			try_find = cur->Find(c);
		}
		if (try_find == nullptr) {
			cur = this;
		}
		else {
			if (try_find->length_ != 0) {
				ans.push_back({i-try_find->length_ + 1, try_find->length_});
				cur = this;
			}
			else {
				cur = try_find;
			}
		}
		++i;
	}
	return ans;
}

TrieNode::~TrieNode()
{
	for (auto& kv : children_) {
		FreeTrieNode(kv.second);
	}
}

void TrieNode::FreeTrieNode(TrieNode* node)
{
	qDebug() << "free";
	delete node;
}

TrieNode* TrieNode::Find(QChar c)
{
	for (auto& kv : children_) {
		if (kv.first == c) {
			return kv.second;
		}
	}
	return nullptr;
}

trie.h

#pragma once

#include <QtWidgets>
#include <queue>

class TrieNode
{
public:
	~TrieNode();

	void Insert(const QString& s);
	void BuildFailPointer();
	bool Contains(const QString& s);
	std::vector<std::pair<int, int>> Match(const QString& text);
private:
	void FreeTrieNode(TrieNode* node);
	TrieNode* Find(QChar c);

	std::unordered_map<QChar, TrieNode*> children_;
	TrieNode* fail_ = nullptr;
	size_t length_ = 0;
};