Cod sursa(job #1667131)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 martie 2016 17:55:33
Problema Aho-Corasick Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.76 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

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

const int TEXT_LEN = 1000005;
const int WORD_LEN = 10005;
const int WCOUNT = 105;

struct trieNode {
    long long pathCount;
    int wIndex;
    trieNode *s[26];
    trieNode *failLink, *outLink;

    trieNode() {
        wIndex = 0;
        pathCount = 0;
        memset(s, 0, sizeof(s));
        failLink = outLink = 0;
    }
};

char text[TEXT_LEN];
char word[WORD_LEN];
trieNode *root = new trieNode();
vector<trieNode*> bfsList;
queue<trieNode*> q;
long long matchCount[WCOUNT];

void addWord(char *str, int index) {
    trieNode *t = root;
    for(int i = 0; str[i] != 0; i++) {
        int cur_char = str[i] - 'a';
        if(t->s[cur_char] == 0) {
            t->s[cur_char] = new trieNode();
        }
        t = t->s[cur_char];
    }
    t->wIndex = index;
}

void failLinkBfs() {
    root->failLink = root->outLink = root;
    for(int i = 0; i < 26; i++) {
        if(root->s[i] != 0) {
            root->s[i]->failLink = root->s[i]->outLink = root;
            q.push(root->s[i]);
        }
    }
    while(!q.empty()) {
        trieNode *cur = q.front();
        bfsList.push_back(cur);
        q.pop();
        for(int i = 0; i < 26; i++) {
           trieNode *fl = cur->failLink;
            if(cur->s[i] != 0) {
                trieNode *son = cur->s[i];
                while(fl != root && fl->s[i] == 0) {
                    fl = fl->failLink;
                }
                if(fl->s[i] != 0) fl = fl->s[i];
                son->failLink = fl;
                if(son->failLink->wIndex) son->outLink = son->failLink;
                else son->outLink = son->failLink->outLink;

                q.push(cur->s[i]);
            }
        }
    }
}

void findMatches() {
    trieNode *t = root;
    for(int i = 0; text[i] != 0; i++) {
        int cur_char = text[i] - 'a';
        while(t != root && t->s[cur_char] == 0) t = t->failLink;
        if(t->s[cur_char] != 0) t = t->s[cur_char];
        t->pathCount++;
    }
}

void dumpPaths() {
    reverse(begin(bfsList), end(bfsList));
    for(auto t : bfsList) {
        t->outLink->pathCount += t->pathCount;
    }
}

void ahoCorasick() {
    failLinkBfs();
    findMatches();
    dumpPaths();

    for(auto t : bfsList) {
        if(t->wIndex) {
            matchCount[t->wIndex] = t->pathCount;
        }
    }
}

int main() {
    int n, i;

    in >> text >> n;
    for(i = 1; i <= n; i++) {
        in >> word;
        addWord(word, i);
    }
    ahoCorasick();
    for(i = 1; i <= n; i++) {
        out << matchCount[i] << '\n';
    }
    return 0;
}