Cod sursa(job #782563)

Utilizator darrenRares Buhai darren Data 28 august 2012 12:01:38
Problema Aho-Corasick Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>

using namespace std;

int N;
string A, B[102];
map<string, string> M;
map<string, vector<string> > R;
map<string, int> P;

void Dfs(string now)
{
	for (vector<string>::iterator it = R[now].begin(); it != R[now].end(); ++it)
	{
		Dfs(*it);
		P[now] += P[*it];
	}
}

int main()
{
	ifstream fin("ahocorasick.in");
	ofstream fout("ahocorasick.out");
	
	fin >> A >> N;
	
	M[string()] = string();
	for (int i = 1; i <= N; ++i)
	{
		fin >> B[i];
		
		string now;
		for (size_t j = 0; j < B[i].size(); ++j)
		{
			now += B[i][j];
			if (M.find(now) == M.end())
				M[now] = string();
		}
	}
	
	for (map<string, string>::iterator it = M.begin(); it != M.end(); ++it)
	{
		for (int i = 0; i < 26; ++i)
			if (M.find(it->first + char(i + 'a')) != M.end())
			{
				string aux = it->second;
				while (aux != string() && M.find(aux + char(i + 'a')) == M.end())
					aux = M[aux];
				
				if (it->first != aux && M.find(aux + char(i + 'a')) != M.end())
				{
					M[it->first + char(i + 'a')] = aux + char(i + 'a');
					R[aux + char(i + 'a')].push_back(it->first + char(i + 'a'));
				}
				else
				{
					M[it->first + char(i + 'a')] = aux;
					R[aux].push_back(it->first + char(i + 'a'));
				}
			}
	}
	
	string now;
	for (size_t i = 0; i < A.size(); ++i)
	{
		while (now != string() && M.find(now + A[i]) == M.end())
			now = M[now];
		if (M.find(now + A[i]) != M.end())
		{
			++P[now + A[i]];
			now += A[i];
		}
	}
	
	Dfs(string());
	
	for (int i = 1; i <= N; ++i)
		fout << P[B[i]] << '\n';
	
	fin.close();
	fout.close();
}