Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, to[1501][128], link[1501], word[1501], sz = 0;
- bool leaf[1501];
- string t;
- void init_trie()
- {
- memset(to, 0, sizeof(to));
- memset(leaf, false, sizeof(leaf));
- memset(link, 0, sizeof(link));
- memset(word, 0, sizeof(word));
- }
- void add_str(string s, int id)
- {
- int u = 0;
- for (int i = 0; i < s.size(); i++)
- {
- int j = s[i];
- if (to[u][s[i]] == 0)
- to[u][j] = ++sz;
- u = to[u][j];
- }
- leaf[u] = true;
- word[u] = id;
- }
- void push_link()
- {
- queue<int> q;
- q.push(0);
- while (!q.empty())
- {
- int u = q.front();
- q.pop();
- int v = link[u];
- leaf[u] |= leaf[v];
- for (int i = 0; i < 128; i++)
- if (to[u][i] != 0)
- {
- link[to[u][i]] = ((u != 0) ? to[v][i] : 0);
- q.push(to[u][i]);
- }
- else
- to[u][i] = to[v][i];
- }
- }
- int search_str(string s)
- {
- int cnt = 0, u = 0;
- for (int i = 0; i < s.size(); i++)
- {
- u = to[u][s[i]];
- int v = u;
- while (leaf[v])
- {
- if (word[v] != 0)
- cnt++;
- v = link[v];
- }
- }
- return cnt;
- }
- int main()
- {
- freopen("find_patterns.inp", "r", stdin);
- freopen("find_patterns.out", "w", stdout);
- init_trie();
- getline(cin, t);
- scanf("%d\n", &n);
- for (int i = 1; i <= n; i++)
- {
- char s[15];
- scanf("%s\n", &s);
- add_str(s, i);
- }
- push_link();
- printf("%d\n", search_str(t));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement