Cod sursa(job #2461250)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 25 septembrie 2019 10:48:24
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct trie{
    trie * ch[27];
    vector<int> indici; //indici cuvinte dictionar care se termina pe nodul respectiv
    int cnt;//numar cuvinte care se termina pe nodul respectiv
    trie *sar;//sare pe nod (cuv sufix maxim)
    trie(){
        for(int i=0; i<=25; i++)
            ch[i]=NULL;
        sar=NULL;
        cnt=0;
    }
}*rad;
char  sir[1000006];
char cuv[100][10005];
int n, ans[100];
vector<trie*> ord;
queue<trie*> q;
void adauga(trie* nod, char *sir, int ind){
    if(*sir==0){
        nod->indici.push_back(ind);
    }
    else{
        if(nod->ch[*sir-'a']==NULL)
            nod->ch[*sir-'a']=new trie();
        adauga(nod->ch[*sir-'a'], sir+1, ind);
    }
}
void sarituri(){
    q.push(rad);
    rad->sar=rad;
    while(!q.empty()){
        trie *nod=q.front(); q.pop();
        ord.push_back(nod);
        for(int i=0; i<=25; i++)
            if((nod->ch[i]!=NULL)&&(nod->ch[i]->sar==NULL)){
               q.push(nod->ch[i]);

            trie *s=nod->sar;
            while((s!=rad)&&(s->ch[i]==NULL))
                s=s->sar;
            if((s->ch[i]!=NULL)&&(nod!=rad))
                nod->ch[i]->sar=s->ch[i];
            else nod->ch[i]->sar=rad;
        }

    }
}
void mergi_pe_text(){
    int m=strlen(sir);
    trie *nod;
    nod=rad;
    for(int i=0; i<m; i++){
        while((nod!=rad)&&(nod->ch[sir[i]-'a']==NULL))
            nod=nod->sar;
        if(nod->ch[sir[i]-'a']==NULL)
           nod=rad;
        else
           nod=nod->ch[sir[i]-'a'];

        nod->cnt++;
    }

}
void act(){
    for(int i=ord.size()-1; i>=0; i--){
        for(int j=0; j<ord[i]->indici.size(); j++)
            ans[ord[i]->indici[j]]=ord[i]->cnt;
        ord[i]->sar->cnt+=ord[i]->cnt;
    }
}
int main()
{
fstream f1 ("ahocorasick.in", ios::in);
fstream f2 ("ahocorasick.out", ios::out);
    rad=new trie();
    f1>>sir>>n;
    for(int i=1; i<=n; i++){
        f1>>cuv[i];
        adauga(rad, cuv[i], i);
    }
    sarituri();
    mergi_pe_text();
    act();
    for(int i=1; i<=n; i++)
        f2<<ans[i]<<"\n";
    return 0;
}