---
tags: codebook
---
{%hackmd theme-dark %}
# AC automaton

## 範例

digraph main{
    node[fontcolor = white;color=white]
    edge[color=white;fontcolor=white]
    bgcolor = "#343434"
    subgraph null{
        node[color=gray;style=dashed;label=nul]
        nul1 nul2 nul3 nul4 nul5 nul6
    }
    subgraph str{
        node[color=yellow]
        aa aaaa aba b baa
    }
/*    subgraph sign{
        node[style=invis;]
        ex1 ex2 ex3 ex4
        ex1->ex2[color=red;style=dashed;label="failure"]
        ex2->ex3[color=aquamarine;style=dashed;label="dictionary"]
        ex4[style=solid;label="pattern";color=yellow]
    }*/
    root->a[label=" a"]
    root->b[label=" b"]
    a->aa[label=" a";]
    a->ab[label=" b"]
    b->ba[label=" a"]
    ab->aba[label=" b"]
    aa->aaa[label=" a"]
    aaa->aaaa[label=" a"]
    ba->baa[label=" a"]
//  {rank=max;newrank=true;ex1 ex2 ex3 ex4}
    {rank=same;root nul1}
    {rank=same;a b}
    {rank=same;aa ab ba}
    {rank=same;aba baa aaa}
    subgraph fail{
        edge[color=red;style=dashed]
        root->nul1
        {a b}->root
        {aa ba}->a
        {aaa baa}->aa
        aaaa->aaa
        aba->ba
        ab->b
    }
    subgraph dictionary{
    edge[color=aquamarine;style=dashed]
        root->nul
        a->nul2
        aa->nul3 
        b->nul4
        ba->nul5
        aba->nul6
        ab->b
        {baa aaa aaaa}->aa
    }
}

## 範例程式碼

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
struct automaton {
	vector<string> data;
	struct node {
		string *data;
		node *fail, *dic, *next[128];
		//initialization
		node(): data(nullptr), next{} {
			fail = dic = nullptr;
		}
	}*root;
	void build(node* cur) {
		if (!cur) return;
		for (size_t i = 0; i != 128; i++) {
			if (!cur->next[i])
				continue;
			//build failure_suffix path
			node* tmp = cur->fail;
			while (tmp && !tmp->next[i])
				tmp = tmp->fail;
			cur->next[i]->fail = tmp ? tmp->next[i] : root;
			//build dictionary_suffix path
			tmp = cur->next[i]->fail;
			cur->next[i]->dic = tmp->data ? tmp : tmp->dic;
			build(cur->next[i]);
		}
	}
	vector<pair<string&, size_t>> operator()(const string& s) {
		vector<pair<string&, size_t>> v;
		node* cur = root;
		for (const auto& i : s) {
			//search by failure_suffix path
			while (cur && !cur->next[size_t(i)])
				cur = cur->fail;
			cur = cur ? cur->next[size_t(i)] : root;
			//search by dictionary_suffic path
			for (node* tmp = cur; tmp; tmp = tmp->dic)
				if (tmp->data)
					v.emplace_back(*tmp->data, &i - &s.front() - tmp->data->size() + 1);
		}
		return v;
	}
	automaton(const vector<string>& v): data(v), root(new node) {
		//build trie
		for (auto& i : data) {
			node* cur = root;
			for (const auto& j : i) {
				if (!cur->next[size_t(j)])
					cur->next[size_t(j)] = new node;
				cur = cur->next[size_t(j)];
			}
			cur->data = &i;
		}
		//build path
		build(root);
	}
};
ostream& operator<<(ostream& os, const vector<pair<auto, auto>>& v) {
	for (const auto& i : v)
		os << setw(5) << i.first << ' ' << setw(2) << i.second << endl;
	return os;
}
int main() {
	string tmp;
	vector<string> vec{"aa", "aaaa", "aba", "b", "baa"};
	automaton t(vec);
	cout << t("aaaababaa") << endl;
	return 0;
}