Cod sursa(job #1560154)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 1 ianuarie 2016 20:38:49
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#define BUF_SIZE 4096
#define MAXN 1000000
#define MAXM 100
#define MAXL 10000
#define SIG 26
struct node{
    int nr;
    struct node *fii[SIG], *fail;
    node(){
        nr=0;
        memset(fii, 0, sizeof fii);
        fail=NULL;
    }
}*root, *q[MAXL*MAXM], *e[MAXM];
char a[MAXN];
int st, dr;
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
inline void makeFail(){
    int i;
    node *x;
    st=0;
    dr=0;
    for(i=0; i<SIG; i++){
        if(root->fii[i]!=NULL){
            q[dr++]=root->fii[i];
            root->fii[i]->fail=root;
        }
    }
    while(st<dr){
        for(i=0; i<SIG; i++){
            if(q[st]->fii[i]!=NULL){
                q[dr++]=q[st]->fii[i];
                x=q[st]->fail;
                while((x!=root)&&(x->fii[i]==NULL)){
                    x=x->fail;
                }
                if(x->fii[i]!=NULL){
                    q[st]->fii[i]->fail=x->fii[i];
                }else{
                    q[st]->fii[i]->fail=root;
                }
            }
        }
        st++;
    }
}
int main(){
    int n, m, i;
    char ch;
    node *p;
    FILE *fout;
    fin=fopen("ahocorasick.in", "r");
    fout=fopen("ahocorasick.out", "w");
    root=new node();
    ch=nextch();
    n=0;
    while(ch!='\n'){
        a[n++]=ch;
        ch=nextch();
    }
    m=read();
    for(i=0; i<m; i++){
        ch=nextch();
        p=root;
        while(ch!='\n'){
            if(p->fii[ch-'a']==NULL){
                p->fii[ch-'a']=new node();
            }
            p=p->fii[ch-'a'];
            ch=nextch();
        }
        e[i]=p;
    }
    makeFail();
    p=root;
    for(i=0; i<n; i++){
        while((p!=root)&&(p->fii[a[i]-'a']==NULL)){
            p=p->fail;
        }
        if(p->fii[a[i]-'a']!=NULL){
            p=p->fii[a[i]-'a'];
        }
        p->nr++;
    }
    for(i=dr-1; i>=0; i--){
        q[i]->fail->nr+=q[i]->nr;
    }
    for(i=0; i<m; i++){
        fprintf(fout, "%d\n", e[i]->nr);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}