Cod sursa(job #2586886)

Utilizator aZvezdaAtanas Dimitrov aZvezda Data 21 martie 2020 18:06:06
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 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;
struct Automaton {
    int leaf[MAX_N];
    int ans[MAX_N], dp[MAX_N], p[MAX_N];
    int link[MAX_N], cnt;
    int to[MAX_N][30];
    vector<int> g[MAX_N];
    Automaton() {cnt = 1; for(int c = 0; c < 30; c ++) {to[0][c] = -1;}}
    void add(string &s, int tme) {
        int curr = 0;
        for(auto itc : s) {
            int it = itc - 'a';
            if(to[curr][it] == -1) {
                for(int c = 0; c < 30; c ++) {to[cnt][c] = -1;}
                to[curr][it] = cnt ++;
            }
            curr = to[curr][it];
        }
        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 ++) {
                int next = to[curr][c];
                if(next == -1) {continue;}
                int l = link[curr];
                while(l != -1 && to[l][c] == -1) {l = link[l];}
                if(l != -1) {l = to[l][c];} else {l = 0;}
                link[next] = l;
                g[l].push_back(next);
                q.push(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;
}