Aho–Corasick algorithm

Aho–Corasick 알고리즘은 특정 문자열에 패턴이 존재하는지를 확인하는 알고리즘이다. 패턴들의 길이의 합을 $m$, 확인하고 싶은 문자열을 $n$이라고 하면 $O(n+m)$의 시간에 패턴이 존재하는지 확인할 수 있다.

자세한 설명은 www.slideshare.net/ssuser81b91b/ahocorasick-algorithm를 참고하자.

class AhoCorasick {
private:
	struct node {
		node* child[26]{};
		node* failure = nullptr;
		node* output = nullptr;
	} root;

	void deallocate(node* p) {
		for (auto q : p -> child) {
			if (q) {
				deallocate(q);
			}
		}

		delete p;
	}

public:
	void add_pattern(string s) {
		node* n = &root;
		for (char c : s) {
			if (!(n -> child[c - 'a'])) {
				n -> child[c - 'a'] = new node;
			}
			n = n -> child[c - 'a'];
		}
		n -> output = n;
	}

	void generate_links() {
		queue<node*> q;
		q.push(&root);

		while (!q.empty()) {
			node* n = q.front(); q.pop();
			for (int i = 0; i < 26; ++i) {
				node* m = n -> child[i];
				if (m) {
					for (node* p = n;; p = p -> failure) {
						if (p == &root) {
							m -> failure = p;
							break;
						}
						if (p -> failure -> child[i]) {
							m -> failure = p -> failure -> child[i];
							break;
						}
					}

					if (m -> failure -> output) {
						m -> output = m -> failure -> output;
					}

					q.push(m);
				}
			}
		}
	}

	bool check(string s) {
		node* n = &root;
		for (char c : s) {
			while (!(n -> child[c - 'a'])) {
				if (n == &root) {
					goto no_char;
				}
				n = n -> failure;
			}

			n = n -> child[c - 'a'];

			if (n -> output) {
				return true;
			}

			no_char:;
		}

		return false;
	}

	~AhoCorasick() {
		for (auto p : root.child) {
			if (p) {
				deallocate(p);
			}
		}
	}
};