Cod sursa(job #1563530)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 6 ianuarie 2016 10:02:40
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define MAXS 1000050
#define MAXN 150
#define MAXCUV 10050

using namespace std;

char s[MAXS], aux[MAXCUV];
int n, sol[MAXN];

struct trieNode
{
    vector<int> pat;
    int hits;
    trieNode *son[30];
    trieNode *suff;
    trieNode()
    {
    	pat.clear();
    	hits = 0;
    	suff = NULL;
    	memset(son, 0, sizeof(son));
    }
} *root = new trieNode();
vector<trieNode*> antiBFS;

void addToTrie(char *p, int pattern, trieNode *crt = root)
{
	if (!*p) {
		crt->pat.push_back(pattern);
		return;
	}
	if (crt->son[*p-'a'] == NULL)
        crt->son[*p-'a'] = new trieNode();
	addToTrie(p+1, pattern, crt->son[*p-'a']);
}

trieNode* getSuff(trieNode *crt, int ind)
{
	if (crt == root)
		return crt;
	if (crt->suff->son[ind])
		return crt->suff->son[ind];
	return getSuff(crt->suff, ind);
}

void constructBounds()
{
	trieNode* crt;
	antiBFS.push_back(root);
	for (int i = 0; i < antiBFS.size(); i++) {
		crt = antiBFS[i];
		for (int i = 0; i < 26; i++)
			if (crt->son[i]) {
				crt->son[i]->suff = getSuff(crt, i);
				antiBFS.push_back(crt->son[i]);
			}
	}
}

trieNode* findNode(trieNode *crt, int ind)
{
	if (crt->son[ind])
		return crt->son[ind];
	if (crt == root)
		return crt;
    return findNode(crt->suff, ind);
}

void solve(trieNode *crt, char *p)
{
	crt->hits++;
	if (!*p) return;
	solve(findNode(crt, *p-'a'), p+1);
}

void prepare()
{
	trieNode* crt;
    for (int i = antiBFS.size()-1; i; --i) {
		crt = antiBFS[i];
		for (int i = 0, sz = crt->pat.size(); i < sz; i++)
			sol[crt->pat[i]] += crt->hits;
		crt->suff->hits += crt->hits;
    }
}

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

    gets(s);
    scanf("%d\n", &n);
    for (int i = 0; i < n; i++) {
        gets(aux);
        addToTrie(aux, i);
    }
    root->suff = root;
    constructBounds();
    solve(root, s);
    prepare();
    for (int i = 0; i < n; i++)
		printf("%d\n", sol[i]);

    return 0;
}