Cod sursa(job #2114854)

Utilizator abel.metinaru112Abel Metinaru abel.metinaru112 Data 25 ianuarie 2018 22:39:18
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.99 kb
#include <iostream>
#include <fstream>

#define nMax 103
#define cuvMax 10003
#define txtMax 1000003

using namespace std;

ifstream fin("ahocorasick.in");
ofstream fin("ahocorasick.out");

int ord[nMax] = {};
int cindex;
char txt[txtMax];

class ahtree{
public:
    char index = 0;
    ahtree *v[26] = {};
    ahtree *failure;
    void insert(char cuv[cuvMax]);
    void fix_root();
    void fix();
    void search();


    void pre();
}*root;

void ahtree :: insert(char cuv[cuvMax]){
    if(!cuv[0]){
        index = cindex;
        return;
    }
    int i = cuv[0] - 'a';
    if(!v[i]){
        v[i] = new ahtree;
    }
    v[i] ->insert(cuv + 1);
    return;
}

void ahtree :: fix(){
    for(int i = 0; i < 26; i ++){
        if(v[i]){
            if(failure ->v[i]){
                v[i] ->failure = failure ->v[i];
            }
            else{
                if(failure != root && root ->v[i]){
                    v[i] ->failure = root ->v[i];
                }
                else{
                    v[i] ->failure = root;
                }
            }
            v[i] ->fix();
        }
    }
    return;
}

void ahtree :: fix_root(){
    failure = nullptr;
    for(int i = 0; i < 26; i ++){
        if(v[i]){
            v[i] ->failure = root;
            v[i] ->fix();
        }
    }
    return;
}

void ahtree :: pre(){
    if(index){
        cout<<" *\n";
    }
    for(int i = 0; i < 26; i ++){
        if(v[i]){
            cout<<(char)(i + 'a')<<"("<<v[i] ->failure<<")";
            v[i] -> pre();
        }
    }
    return;
}

void ahtree :: search(){
    if(index){
        ++ ord[index];
    }
    if(!txt[cindex]){
        return;
    }
    int i = txt[cindex] - 'a';
    if(v[i]){
        if(failure && failure ->index){
            ++ ord[failure ->index];
        }
        ++ cindex;
        v[i] ->search();
    }
    else{
        if(failure == nullptr){
            ++ cindex;
            search();
        }
        else{
            failure ->search();
        }
    }
    return;
}

void search(){
    ahtree *now;
    int i = 0, j;
    while(txt[i]){
        j = txt[i] - 'a';
        if(now ->v[j]){
            now = now ->v[j];
            ++ i;
        }
        else{
            if(now ->failure){
                now = now ->failure;
            }
            else{
                ++ i;
            }
        }
        if(now ->index){
            ++ ord[now ->index];
        }
        for(ahtree *it = now ->failure; it; it = it ->failure){
            if(it ->index){
                ++ ord[it ->index];
            }
        }
    }
    return;
}

int main(){
    int n;
    char cuv[cuvMax];
    root = new ahtree;
    fin>>txt>>n;
    for(cindex = 1; cindex <= n; cindex ++){
        fin>>cuv;
        root ->insert(cuv);
    }
    root ->fix_root();
    search();
    for(int i = 1; i <= n; i ++){
        fout<<ord[i]<<"\n";
    }
	return 0;
}