Cod sursa(job #824861)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 27 noiembrie 2012 03:01:12
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstring>
#include <fstream>
#include <iostream>
#include <new>
#include <string>
#include <vector>

using namespace std;

struct node {
	vector<int> index;
	int cnt;
	node * fail;
	node * next[26];
};

node * root;
node * Q[26 * 100 * 10000];
int front, back;

int n;
string A, w;
int ans[101];

inline void bfs1() {
	root->fail = root;
	Q[back++] = root;
	while (back - front > 0) {
		node * u = Q[front++];
		for (int i = 0; i < 26; i++) {
			node * v = u->next[i];
			if (v != 0) {
				node * f = u->fail;
				while (f != root && f->next[i] == 0) {
					f = f->fail;
				}
				if (f->next[i] != 0 && f->next[i] != v) {
					f = f->next[i];
				}
				v->fail = f;
				Q[back++] = v;
			}
		}
	}
}

inline void bfs2() {
	while (back) {
		node * u = Q[--back];
		u->fail->cnt += u->cnt;
		for (size_t i = 0; i < u->index.size(); i++) {
			ans[u->index[i]] = u->cnt;
		}
	}
}
int main() {
	ifstream cin("ahocorasick.in");
	ofstream cout("ahocorasick.out");
	cin >> A;
	cin >> n;
	root = new node();
	node * current;
	for (int i = 1; i <= n; i++) {
		cin >> w;
		current = root;
		for (size_t j = 0; j < w.size(); j++) {
			int c = w[j] - 'a';
			if (current->next[c] == 0) {
				current->next[c] = new node();
			}
			current = current->next[c];
		}
		current ->index.push_back(i);
	}
	bfs1();
	current = root;
	for (size_t i = 0; i < A.size(); i++) {
		int c = A[i] - 'a';
		while (current != root && current->next[c] == 0) {
			current = current->fail;
		}
		if (current->next[c] != 0) {
			current = current->next[c];
		}
		current->cnt++;
	}
	bfs2();
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}