Cod sursa(job #1668624)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 29 martie 2016 22:12:51
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include<cstdio>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
const int L=1000000;
const int M=100000;
const int N=100;
const int SIGMA=30;
struct Node{
    public:
        vector<int>w;
        Node* v[SIGMA];
        Node* fail;
        int nr;
        Node(){
            w.clear();
            for(int i=0;i<SIGMA;i++)
                v[i]=NULL;
            nr=0;
        }
};
stack<Node*>st;
queue<Node*>q;
int res[N+1];
Node *T=new Node;
char s[L+1];
char ss[M+1];
int n;
void set_fail(Node* dad,int c){
    Node*son=dad->v[c];
    if(dad==T){
        son->fail=T;
        return;
    }
    Node*curr=dad->fail;
    while(curr->v[c]==NULL&&curr!=T)
        curr=curr->fail;
    if(curr->v[c]!=NULL)
        son->fail=curr->v[c];
    else
        son->fail=T;
}
void bfs(){
    q.push(T);
    while(!q.empty()){
        Node* dad=q.front();
        st.push(dad);
        q.pop();
        for(int i=0;i<SIGMA;i++){
            Node*son=dad->v[i];
            if(son!=NULL){
                set_fail(dad,i);
                q.push(son);
            }
        }
    }
}
void aho_corasick(){
    int l=strlen(s);
    Node*curr=T;
    for(int i=0;i<l;i++){
        int c=s[i]-'a';
        while(curr->v[c]==NULL&&curr!=T)
            curr=curr->fail;
        if(curr->v[c]!=NULL){
            curr=curr->v[c];
            curr->nr++;
        }
    }
}
int main(){
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    gets(s);
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++){
        gets(ss);
        int m=strlen(ss);
        Node*curr=T;
        for(int j=0;j<m;j++){
            int c=ss[j]-'a';
            if(curr->v[c]==NULL)
                curr->v[c]=new Node();
            curr=curr->v[c];
        }
        curr->w.push_back(i);
    }
    bfs();
    aho_corasick();
    T->fail=T;
    while(!st.empty()){
        Node* dad=st.top();
        st.pop();
        dad->fail->nr+=dad->nr;
        for(unsigned int i=0;i<dad->w.size();i++)
            res[dad->w[i]]+=dad->nr;
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",res[i]);
    return 0;
}