Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define TASK "1"
- using namespace std;
- struct aho_auto {
- struct node {
- unordered_map<int, int> to;
- unordered_map<int, int> go;
- int suff;
- int info;
- node() {
- info = 0;
- }
- };
- vector<node> v;
- aho_auto(vector<string> &ss) {
- v.push_back(node());
- for (auto s : ss) {
- int h = 0;
- for (int i = 0; i < (int)s.size(); i++) {
- int c = s[i];
- if (v[h].to.count(c) == 0) {
- v.push_back(node());
- v[h].to[c] = v.size() - 1;
- }
- h = v[h].to[c];
- }
- v[h].info++;
- }
- queue<int> q;
- q.push(0);
- q.push(0);
- q.push(0);
- while (q.size() > 0) {
- int x = q.front();
- q.pop();
- int parent = q.front();
- q.pop();
- int c = q.front();
- q.pop();
- if (x == 0 || parent == 0) {
- v[x].suff = 0;
- } else {
- int t = v[parent].suff;
- while (t > 0 && v[t].to.count(c) == 0) t = v[t].suff;
- v[x].suff = v[t].to[c];
- }
- v[x].info += v[v[x].suff].info;
- for (pair<int, int> y : v[x].to) {
- q.push(y.second);
- q.push(x);
- q.push(y.first);
- }
- }
- }
- int size() {
- return v.size();
- }
- int go(int from, int c) {
- if (v[from].to.count(c) != 0) return v[from].to[c];
- if (from == 0) return 0;
- if (v[from].go.count(c) != 0) return v[from].go[c];
- int ret = go(v[from].suff, c);
- return v[from].go[c] = ret;
- }
- int get_info(int x) {
- return v[x].info;
- }
- };
- int main(){
- #ifdef home
- freopen(TASK".in","r",stdin);
- freopen(TASK".out","w",stdout);
- #endif
- ios::sync_with_stdio(false);
- int n;
- cin >> n;
- vector<string> s(n);
- for (int i = 0; i < n; i++) cin >> s[i];
- string t;
- cin >> t;
- auto a = aho_auto(s);
- int ans = 0;
- int x = 0;
- for (int i = 0; i < (int)t.size(); i++) {
- x = a.go(x, t[i]);
- ans += a.get_info(x);
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement