Cod sursa(job #2587120)

Utilizator bigmixerVictor Purice bigmixer Data 22 martie 2020 00:56:55
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.43 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;
const int modu=1999999973;
const int modul=998244353;

int n,ans[105];
string s,t[105];

struct Trie{
    int val,parinte,trail;
    vector<int>cont;
    int a[27];
    Trie(){
        val = parinte = trail=0;
    }
}tz;

vector<Trie>vecc;

void buildtrie(){
    vecc.push_back(tz);
    for(int i=1;i<=n;i++){
        int curr=0;
        for(int j=0;j<t[i].size();j++){
            if(vecc[curr].a[t[i][j]-'a']){
                curr=vecc[curr].a[t[i][j]-'a'];
            }
            else{
                vecc[curr].a[t[i][j]-'a']=vecc.size();
                vecc.push_back(tz);
                vecc[vecc.size()-1].val=(t[i][j]-'a');
                vecc[vecc.size()-1].parinte=curr;
                curr=vecc.size()-1;
            }
            if(j==(t[i].size()-1)) vecc[curr].cont.push_back(i);
        }
    }
}



void bfs(){
    queue<int>q;
    q.push(0);
    bitset<260000>viz;
    viz[0]=1;
    while(q.size()){
        int x=q.front();
        if(x>=1){
            int v=vecc[x].val;
            int y=vecc[vecc[x].parinte].trail;
            if(vecc[x].parinte!=0)while(true){
                if(vecc[y].a[v]>0){
                    vecc[x].trail=vecc[y].a[v];
                    for(int i=0;i<vecc[vecc[y].a[v]].cont.size();i++){
                        vecc[x].cont.push_back(vecc[vecc[y].a[v]].cont[i]);
                    }
                    break;
                }
                if(vecc[y].trail==y) break;
                y=vecc[y].trail;
            }
        }
        for(int i=0;i<=25;i++){
            if(vecc[x].a[i]>=1 && viz[vecc[x].a[i]]==0){
                q.push(vecc[x].a[i]);
                viz[vecc[x].a[i]]=1;
            }
        }
        q.pop();
    }
    return;
}

void calc(){
    int indx=0;
    for(int i=0;i<s.size();i++){
        if(vecc[indx].a[s[i]-'a']){
            indx=vecc[indx].a[s[i]-'a'];
            for(int j=0;j<vecc[indx].cont.size();j++){
                ans[vecc[indx].cont[j]]++;
            }
        }
        else{
            while(true){
                if(indx==vecc[indx].trail) break;
                indx=vecc[indx].trail;
                if(vecc[indx].a[s[i]-'a']){
                    indx=vecc[indx].a[s[i]-'a'];
                    for(int j=0;j<vecc[indx].cont.size();j++){
                        ans[vecc[indx].cont[j]]++;
                    }
                    break;
                }
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ifstream cin("ahocorasick.in");
    ofstream cout("ahocorasick.out");
    cin >> s >> n;
    for(int i=1;i<=n;i++){
        cin >> t[i];
    }
    buildtrie();
    bfs();
    calc();
    for(int i=1;i<=n;i++) cout << ans[i] << '\n';
}