Cod sursa(job #1093080)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 27 ianuarie 2014 18:46:21
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

const int A = 1100000;
const int B = 11000;
const int N = 105;
const int S = 26;

struct trie {
    vector<int> cuv;
    trie *f[S], *pref;
    int nr;

    trie() {
        nr = 0;
        pref = 0;
        for(int i = 0; i < S; ++i)
            f[i] = 0;
    }
};

char a[A], b[B];
int n, rez[N], pc;
trie rad;

void add(trie &r, int poz) {
    if(!b[poz]) {
        r.cuv.push_back(pc);
        return;
    }

    if(!r.f[b[poz] - 'a'])
        r.f[b[poz] - 'a'] = new trie;

    add(*r.f[b[poz] - 'a'], poz + 1);
}

void cp(trie &r, int ver, int lit, trie *lastp) {
    if(ver)
        r.pref = &rad;
    else {
        while(lastp != &rad && !lastp->f[lit])
            lastp = lastp->pref;

        r.pref = lastp->f[lit];
    }

    for(int i = 0; i < 26; ++i)
        if(r.f[i])
            cp(*r.f[i], 0, i, r.pref);
}

void calcpref() {
    int i;

    for(i = 0; i < S; ++i) if(rad.f[i])
        cp(*rad.f[i], 1, i, 0);
}

void df(trie &r) {
    int i;

    for(i = 0; i < S; ++i) if(r.f[i]) {
        df(*r.f[i]);
        r.nr += r.f[i]->nr;
    }

    for(vector<int>::iterator it = r.cuv.begin(); it != r.cuv.end(); ++it)
        rez[*it] = r.nr;
}

int main() {
    int i;
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    cin.getline(a, A);

    cin >> n;
    cin.get();

    for(i = 1; i <= n; ++i) {
        pc = i;
        cin.getline(b, B);
        add(rad, 0);
    }

    calcpref();

    trie *pozc = &rad;

    for(i = 0; a[i]; ++i){
        a[i] -= 'a';
        bool ver = 1;

        while(pozc != &rad && !pozc->f[a[i]]) {
            pozc = pozc->pref;
            pozc->nr++;
            ver = 0;
        }

        if(ver)
            pozc->nr--;

        pozc = pozc->f[a[i]];
        pozc->nr++;
    }
    while(pozc != &rad) {
        pozc = pozc->pref;
        pozc->nr++;
    }

    df(rad);

    for(i = 1; i <= n; ++i)
        cout << rez[i] << "\n";

    return 0;
}