Cod sursa(job #1409930)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 30 martie 2015 19:38:19
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

const int maxn = 1000005;
const int maxlg = 10005;
const int sigma = 26;

char a[maxn], word[maxlg];
int n, ans[maxn];

struct trie {
	trie *sons[sigma];
	trie *fail;
	int cnt;
	vector <int> matches;
	trie () {
		memset(sons, 0, sizeof(sons));
		cnt = 0;
		matches.clear();
	}
} *root = new trie();

vector < trie * > q;

inline void insert(trie *node, char *s, int ind) {
	if(!*s) {
		node->matches.push_back(ind);
		return ;
	}
	int son = *s - 'a';
	if(!node->sons[son])
		node->sons[son] = new trie();
	insert(node->sons[son], s + 1, ind);
}

inline void buildfail() {
	trie * node = root;
	node->fail = node;
	q.push_back(node);
	for(int i = 0 ; i < q.size() ; ++ i) {
		node = q[i];
		for(int son = 0 ; son < sigma ; ++ son)
			if(node->sons[son]) {
				trie *k = node->fail;
				while(k != root && !k->sons[son])
					k = k->fail;
				if(node != root && k->sons[son])
					k = k->sons[son];
				node->sons[son]->fail = k;
				q.push_back(node->sons[son]);
			}
	}
}

inline void aho() { /// ahoi marinari
	trie *k = root;
	for(int i = 1 ; a[i] ; ++ i) {
		int son = a[i] - 'a';
		while(k != root && !k->sons[son])
			k = k->fail;
		if(k->sons[son])
			k = k->sons[son];
		++ k->cnt;
	}
}

inline void revbfs() {
	trie *node;
	for(int i = q.size() - 1 ; i >= 0 ; -- i) {
		node = q[i];
		node->fail->cnt += node->cnt;
		for(int j = 0 ; j < node->matches.size() ; ++ j) {
			ans[node->matches[j]] = node->cnt;
		}
	}
}

int main() {
	freopen("ahocorasick.in", "r", stdin);
	freopen("ahocorasick.out", "w", stdout);
	cin.getline(a + 1, maxn);
	cin >> n;
	cin.get();
	for(int i = 1 ; i <= n ; ++ i) {
		cin.getline(word, maxlg);	
		insert(root, word, i);
	}
	buildfail();
	aho();
	revbfs();
	for(int i = 1 ; i <= n ; ++ i)
		cout << ans[i] << '\n';
}