Cod sursa(job #2115679)

Utilizator abel.metinaru112Abel Metinaru abel.metinaru112 Data 26 ianuarie 2018 23:42:56
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

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

using namespace std;

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

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

class ahtree{
public:
    vector < char > index;
    ahtree *v[26] = {};
    ahtree *failure;
}*root;

void insert(char cuv[cuvMax], int cindex){
    int j;
    ahtree *now = root;
    for(int i = 0; cuv[i]; i ++){
        j = cuv[i] - 'a';
        if(!now ->v[j]){
            now ->v[j] = new ahtree;
        }
        now = now ->v[j];
    }
    (now ->index).push_back(cindex);
}

void fix_failure(){
    queue < ahtree* > Q;
    ahtree *now = root, *it;
    root ->failure = nullptr;
    for(int i = 0; i < 26; i ++){
        if(root ->v[i]){
            root ->v[i] ->failure = root;
            Q.push(root ->v[i]);
        }
    }
    while(!Q.empty()){
        now = Q.front();
        Q.pop();
        if((now ->failure ->index).size()){
            for(int i = 0; i < (now ->failure ->index).size(); i ++){
                (now -> index).push_back((now ->failure ->index)[i]);
            }
        }
        for(int i = 0; i < 26; i ++){
            if(now ->v[i]){
                for(it = now ->failure; it; it = it ->failure){
                    if(it ->v[i]){
                        break;
                    }
                }
                if(it){
                    now ->v[i] ->failure = it ->v[i];
                }
                else{
                    now ->v[i] ->failure = root;
                }
                Q.push(now ->v[i]);
            }
        }
    }
    return;
}


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

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