Cod sursa(job #1222008)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 21 august 2014 21:41:03
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100010
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

string A, B;
int N, App[111];

struct Node {
	int X;
	vector<int> Words;
	struct Node *F[26], *Prev;
	Node() {
		memset(F, 0, sizeof(F));
		Prev = 0;
		X = 0;
		Words.resize(0);
	}
};

struct Trie{
	Node *R;
	vector<Node*> Q;
	
	Trie() {
		R = new Node();
		Q.resize(0);
	}
	
	void Add(string B, int K) {
		Node *It = R;
		int U;
		for (int i = 0; i < B.length(); i++) {
			U = B[i]-'a';
			if (It->F[U] == NULL) {
				It->F[U] = new Node();
			}
			It = It->F[U];
		}
		It->Words.push_back(K);
	}
	
	void BFS() {
		Node *It, *T;
		int U;
		R->Prev = R;
		Q.push_back(R);
		for (int i = 0; i < Q.size(); i++) {
			It = Q[i];
			for (int U = 0; U < 26; U++) 
			if (It->F[U]) {
				for (T = It->Prev; T != R && T->F[U] == 0; T = T->Prev);
				if (T->F[U] != 0 && T->F[U] != It->F[U]) T = T->F[U];
				It->F[U]->Prev = T;
				Q.push_back(It->F[U]);
			}
		}
		R->Prev = 0;
	}
	
	void Calculate() {
		Node *It = R;
		int U;
		for (int i = 0; i < A.length(); i++) {
			U = A[i]-'a';
			while (It != R && It->F[U] == 0) It = It->Prev;
			if (It->F[U]) {
				It = It->F[U];
				It->X++;
			}
		}
	}
	
	void Extract() {
		Node *It;
		for (int i = Q.size() - 1; i >= 0; i--) {
			It = Q[i];
			for (int j = 0; j < It->Words.size(); j++) {
				App[It->Words[j]] = It->X;
			}
			if (It->Prev) It->Prev->X += It->X;
		}
	}
	
} *T;

int main() {
	
	T = new Trie();
	
	f >> A;
	f >> N;
	for (int i = 1; i <= N; i++) {
		f >> B;
		T->Add(B, i);
	}
	T->BFS();
	T->Calculate();
	T->Extract();
	
	for (int i = 1; i <= N; i++) {
		g << App[i] << "\n";
	}
		
	return 0;
}