Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <unordered_map>
- using namespace std;
- struct Tree {
- int flag;
- Tree* next[26], *go[26];
- Tree *parent, *link;
- char ch;
- Tree(char ch, Tree *parent) : ch(ch), parent(parent), flag(0), link(0) {
- for (int i = 0; i < 26; ++i) {
- next[i] = NULL;
- go[i] = NULL;
- }
- }
- };
- Tree *root = new Tree(0, 0);
- Tree *go(Tree *v, char c);
- void add(Tree *root, string s) {
- for (char c : s) {
- auto it = root->next[c - 'a'];
- if (it != NULL) {
- root = it;
- } else {
- Tree *v = new Tree(c, root);
- root->next[c - 'a'] = v;
- root = v;
- }
- }
- root->flag++;
- }
- Tree *link(Tree *v) {
- if (!v->link) {
- if (v->parent == root || v == root) {
- v->link = root;
- } else {
- v->link = go(link(v->parent), v->ch);
- }
- }
- return v->link;
- }
- Tree *go(Tree *v, char c) {
- if (v->go[c - 'a'] == NULL) {
- if (v->next[c - 'a'] != NULL) {
- v->go[c - 'a'] = v->next[c - 'a'];
- } else {
- v->go[c - 'a'] = (v == root ? root : go(link(v), c));
- }
- }
- return v->go[c - 'a'];
- }
- unordered_map<Tree*, int> is_term;
- int is_terminal(Tree *v) {
- if (v == root) {
- return 0;
- }
- if (is_term.find(v) == is_term.end()) {
- is_term[v] = (v->flag + is_terminal(link(v)));
- }
- return is_term[v];
- }
- vector<pair<int, char>> g[(int)1e5];
- long long ans = 0;
- unordered_map<Tree*, int> been;
- void dfs(int v, Tree *now) {
- ans += (long long)is_terminal(now);
- for (auto x : g[v]) {
- dfs(x.first, go(now, x.second));
- }
- }
- int main() {
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- int k;
- cin >> k;
- for (int j = 0; j < k; ++j) {
- int to;
- char c;
- cin >> to >> c;
- to--;
- g[i].push_back({to, c});
- }
- }
- cin >> n;
- string s;
- for (int i = 0; i < n; ++i) {
- cin >> s;
- add(root, s);
- }
- dfs(0, root);
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement