Cod sursa(job #2586896)

Utilizator aZvezdaAtanas Dimitrov aZvezda Data 21 martie 2020 18:13:46
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 kb
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}

const int MAX_N = 1e5 + 10, ALPH = 30;
struct Automaton {
    int ans[MAX_N], dp[MAX_N], p[MAX_N];
    int link[MAX_N], cnt, to[MAX_N][ALPH];
    int leaf[MAX_N];
    vector<int> g[MAX_N];
    Automaton() {
        cnt = 1;
        for(int i = 0; i < MAX_N; i ++) {
            fill_n(to[i], ALPH, -1);
        }
    }
    void add(string &s, int tme) {
        int curr = 0;
        for(auto it : s) {
            int c = it - 'a';
            if(to[curr][c] == -1) {
                to[curr][c] = cnt ++;
            }
            curr = to[curr][c];
        }
        leaf[curr] = tme;
        p[tme] = curr;
    }
    void pushLink() {
        queue<int> q; q.push(0);
        link[0] = -1;
        while(!q.empty()) {
            int curr = q.front(); q.pop();
            for(int c = 0; c < 30; c ++) if(to[curr][c] != -1) {
                int next = to[curr][c];
                int l = link[curr];
                while(l && to[l][c] == -1) {l = link[l];}
                if(to[l][c] != -1) {l = to[l][c];}
                link[next] = l;
                q.push(next);
                g[l].push_back(next);
            }
        }
    }
    void dfs(int x) {
        for(auto it : g[x]) {
            dfs(it);
            dp[x] += dp[it];
        }
    }
    void getAns(string &s) {
        int curr = 0;
        for(auto itc : s) {
            int c = itc - 'a';
            while(curr && to[curr][c] == -1) {curr = link[curr];}
            if(to[curr][c] != -1) {curr = to[curr][c];}
            dp[curr] ++;
        }
        dfs(0);
    }
};

Automaton au;

string s;

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ofstream myfile;
    myfile.open ("ahocorasick.out");
    ifstream myFileIn;
    myFileIn.open ("ahocorasick.in");

    myFileIn >> s;
    int n;
    myFileIn >> n;
    for(int i = 0; i < n; i ++) {
        string x;
        myFileIn >> x;
        au.add(x, i);
    }
    au.pushLink();
    au.getAns(s);
    for(int i = 0; i < n; i ++) {
        myfile << au.dp[au.p[i]] << endl;
    }
    return 0;
}