// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/aho_corasick
#include "Tree/aho_corasick.hpp"
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin >> N;
AhoCorasick<char> aho_cora;
vector<string> S(N);
vector<int> terminal_node_ids(N);
for (int i = 0; i < N; i++)
{
cin >> S[i];
terminal_node_ids[i] = aho_cora.insert(S[i]);
}
aho_cora.build();
cout << aho_cora.size() << endl;
for (int i = 1; i < aho_cora.size(); i++)
{
cout << aho_cora.parent(i) << " " << aho_cora.get_suffix_link(i) << endl;
}
for (int i = 0; i < N; i++)
{
cout << terminal_node_ids[i] << " ";
}
cout << endl;
return 0;
}
#line 1 "test/Tree/aho_corasick/yosupo-aho_corasick.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/aho_corasick
#line 1 "Tree/aho_corasick.hpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "Tree/trie.hpp"
using namespace std;
template <class T>
struct Trie
{
struct Node
{
// 子ノードへの遷移
unordered_map<T, int> next_node_ids;
// 親ノードのID
// root の parent は -1
int parent = -1;
// parent からこのノードへ遷移するときに使った値
// root では意味を持たない
T transition_value{};
// このノードを通過する文字列の個数
int pass_count = 0;
// このノードで終端する文字列の個数
int end_count = 0;
Node() {};
Node(int parent, const T &transition_value)
: parent(parent), transition_value(transition_value) {};
};
vector<Node> nodes;
Trie() : nodes()
{
nodes.push_back(Node());
};
template <typename Container>
requires same_as<typename Container::value_type, T>
int insert(const Container &v)
{
int node_id = 0;
nodes[node_id].pass_count++;
for (const auto &c : v)
{
if (!nodes[node_id].next_node_ids.contains(c))
{
int next_node_id = nodes.size();
nodes[node_id].next_node_ids[c] = next_node_id;
// 新しく作るノードは、現在のノードを親として持つ
nodes.push_back(Node(node_id, c));
}
node_id = nodes[node_id].next_node_ids[c];
nodes[node_id].pass_count++;
}
nodes[node_id].end_count++;
// 挿入した列に対応する終端ノードIDを返す
return node_id;
}
template <typename Container, typename Func>
requires same_as<typename Container::value_type, T> && invocable<Func, int, bool>
void iterate_prefix(const Container &v, Func f)
{
int node_id = 0;
for (auto itr = v.begin(); itr != v.end(); itr++)
{
if (!nodes[node_id].next_node_ids.contains(*itr))
{
return;
}
node_id = nodes[node_id].next_node_ids[*itr];
// 第2引数は、現在のノードが入力列 v の終端かどうか
f(node_id, next(itr) == v.end());
}
}
template <typename Container>
requires same_as<typename Container::value_type, T>
void erase_subtrie(const Container &prefix)
{
int node_id = 0;
vector<int> ancestors;
for (const auto &c : prefix)
{
ancestors.push_back(node_id);
if (!nodes[node_id].next_node_ids.contains(c))
{
return;
}
node_id = nodes[node_id].next_node_ids[c];
}
int removed_pass_count = nodes[node_id].pass_count;
// prefix 以下の部分木を論理的に削除する
nodes[node_id].pass_count = 0;
nodes[node_id].end_count = 0;
nodes[node_id].next_node_ids.clear();
// 祖先の通過回数から、削除した部分木の通過回数を引く
for (const auto &ancestor : ancestors)
{
nodes[ancestor].pass_count -= removed_pass_count;
}
}
};
#line 5 "Tree/aho_corasick.hpp"
template <class T>
struct AhoCorasick
{
Trie<T> trie;
// suffix_link[v]:
// str(v) の真の接尾辞のうち、Trie に存在する最長のものに対応するノードID
vector<int> suffix_link;
// matched[v]:
// v に到達した時点で、何らかの登録済みパターンが末尾にマッチしているか
vector<bool> matched;
// build 後に true
bool built = false;
AhoCorasick() = default;
template <typename Container>
requires same_as<typename Container::value_type, T>
int insert(const Container &pattern)
{
built = false;
return trie.insert(pattern);
}
void build()
{
const int node_count = trie.nodes.size();
suffix_link.assign(node_count, 0);
matched.assign(node_count, false);
for (int node_id = 0; node_id < node_count; node_id++)
{
matched[node_id] = trie.nodes[node_id].end_count > 0;
}
queue<int> que;
// root の子の suffix link は root
for (const auto &[value, child] : trie.nodes[0].next_node_ids)
{
suffix_link[child] = 0;
que.push(child);
}
while (!que.empty())
{
int node_id = que.front();
que.pop();
// suffix link 先でマッチしているなら、このノードもマッチ状態
matched[node_id] = matched[node_id] || matched[suffix_link[node_id]];
for (const auto &[value, child] : trie.nodes[node_id].next_node_ids)
{
suffix_link[child] = find_next(suffix_link[node_id], value);
que.push(child);
}
}
built = true;
}
int move(int node_id, const T &value) const
{
assert(built);
return find_next(node_id, value);
}
bool is_matched(int node_id) const
{
assert(built);
return matched[node_id];
}
int get_suffix_link(int node_id) const
{
assert(built);
return suffix_link[node_id];
}
int parent(int node_id) const
{
return trie.nodes[node_id].parent;
}
T transition_value(int node_id) const
{
return trie.nodes[node_id].transition_value;
}
int size() const
{
return trie.nodes.size();
}
private:
int find_next(int node_id, const T &value) const
{
while (node_id != 0 && !trie.nodes[node_id].next_node_ids.contains(value))
{
node_id = suffix_link[node_id];
}
if (trie.nodes[node_id].next_node_ids.contains(value))
{
return trie.nodes[node_id].next_node_ids.at(value);
}
return 0;
}
};
#line 5 "test/Tree/aho_corasick/yosupo-aho_corasick.cpp"
using namespace std;
int main()
{
int N;
cin >> N;
AhoCorasick<char> aho_cora;
vector<string> S(N);
vector<int> terminal_node_ids(N);
for (int i = 0; i < N; i++)
{
cin >> S[i];
terminal_node_ids[i] = aho_cora.insert(S[i]);
}
aho_cora.build();
cout << aho_cora.size() << endl;
for (int i = 1; i < aho_cora.size(); i++)
{
cout << aho_cora.parent(i) << " " << aho_cora.get_suffix_link(i) << endl;
}
for (int i = 0; i < N; i++)
{
cout << terminal_node_ids[i] << " ";
}
cout << endl;
return 0;
}
test/Tree/aho_corasick/yosupo-aho_corasick.cpp