Cod sursa(job #1102757)

Utilizator stefanzzzStefan Popa stefanzzz Data 9 februarie 2014 14:39:17
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#define MAXC 26
#define MAXN 105
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

struct nod{
    int nr;
    vector<int> cuv;
    nod *fiu[MAXC],*fail;
    nod(){
        int i;
        nr=0;
        for(i=0;i<MAXC;i++)
            fiu[i]=NULL;
        fail=NULL;}};

nod *start,*a,*b;
queue<nod *> q;
vector<nod *> aq;
int n,x,sol[MAXN];
string s,s1;

int main()
{
    int i,j;
    f>>s>>n;
    start=new nod;
    for(i=1;i<=n;i++){
        f>>s1;
        a=start;
        for(j=0;j<s1.size();j++){
            x=s1[j]-'a';
            if(a->fiu[x]==NULL)
                a->fiu[x]=new nod;
            a=a->fiu[x];}
        a->cuv.push_back(i);}
    start->fail=start;
    for(i=0;i<MAXC;i++)
        if(start->fiu[i]!=NULL){
            start->fiu[i]->fail=start;
            q.push(start->fiu[i]);}
    while(!q.empty()){
        a=q.front();
        q.pop();
        aq.push_back(a);
        for(i=0;i<MAXC;i++){
            if(a->fiu[i]==NULL)
                continue;
            b=a->fail;
            while(b!=start&&b->fiu[i]==NULL)
                b=b->fail;
            if(b->fiu[i]==NULL)
                a->fiu[i]->fail=start;
            else
                a->fiu[i]->fail=b->fiu[i];
            q.push(a->fiu[i]);}}
    a=start;
    for(i=0;i<s.size();i++){
        x=s[i]-'a';
        while(a!=start&&a->fiu[x]==NULL)
            a=a->fail;
        if(a->fiu[x]!=NULL)
            a=a->fiu[x];
        a->nr++;}
    for(i=aq.size()-1;i>=0;i--){
        a=aq[i];
        for(j=0;j<a->cuv.size();j++)
            sol[a->cuv[j]]+=a->nr;
        a->fail->nr+=a->nr;}
    for(i=1;i<=n;i++)
        g<<sol[i]<<'\n';
    f.close();
    g.close();
    return 0;
}