Cod sursa(job #1563254)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 5 ianuarie 2016 20:00:42
Problema Aho-Corasick Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#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;
    trieNode *son[30];
    trieNode *suff;
    trieNode()
    {
    	pat.clear();
    	suff = NULL;
    	memset(son, 0, sizeof(son));
    }
} *root = new trieNode();

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)
{
	if (crt == NULL)
		return;
    for (int i = 0; i < 26; i++)
        if (crt->son[i]) {
			crt->son[i]->suff = getSuff(crt, i);
			constructBounds(crt->son[i]);
        }
}

void updateSolution(trieNode *crt)
{
	if (crt == root) return;
	for (int i = 0; i < crt->pat.size(); i++)
		sol[crt->pat[i]]++;
	updateSolution(crt->suff);
}

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)
{
	updateSolution(crt);
	if (!*p) return;
    if (crt->son[*p-'a'])
		solve(crt->son[*p-'a'], p+1);
	else
        solve(findNode(crt->suff, *p-'a'), p+1);
}

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);
    }
    constructBounds(root);
    root->suff = root;
    solve(root, s);
    for (int i = 0; i < n; i++)
		printf("%d\n", sol[i]);

    return 0;
}