Cod sursa(job #2077841)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 28 noiembrie 2017 17:52:44
Problema Aho-Corasick Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 5 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

#define greenv dictSuffix
#define bluev suffix

using namespace std;

const int NLIM = 1e6 + 10;

string str;
string s;
int n;

// every node has a number, this thing has edges in it
// graph[nod].size() edges from nod, in graph[nod]
vector< int > graph[NLIM]; // +
int nodi = 1;// this is for knowing the number of the next node we are adding
int parent[NLIM]; // +
// suffix arcs ( blue )
int suffix[NLIM];
// dictionary suffix arcs ( green )
int dictSuffix[NLIM];
// word[nod] -> which word is in nod ( if there is a word in it ) ( idxd from 1 )
int wordi = 1; // this is for filling up word
int word[NLIM]; // +
// nodc[nod] -> character that is in nod
char nodc[NLIM]; // +

// the number of appearances of the words
int res[NLIM];


// returns the child of nod that has c char in it ( or -1 if no such thing exists )
int getChild( int nod, char c )
{
	for( int j = 0; j < graph[nod].size(); ++j )
		if( nodc[graph[nod][j]] == c )
			return graph[nod][j];
	return -1;
}

// gets next node during the matching phase if the next char is c and we were on nod
int nextNode( int nod, char c )
{
	int nnod = -1;
	// try to get the child of nod
	// if nod doesn't have a suitable child we go to it's suffix's child
	while( nnod == -1 && nod != -1 )// if we get to root and don't find it's child we have to stop
	{
		nnod = getChild( nod, c );
		nod = suffix[nod];
	}

	// if we didn't find a child then we go to root
	if( nnod == -1 )
		return 0;
	return nnod;
}

// add the word s ( global ) to the tree
void addWord()
{
	// traverse the graph with this var
	int nod = 0;
	// iterate over the characters in the word
	for( int i = 0; i < s.size(); ++i )
	{
		// go to next node in word
		int nnod = getChild( nod, s[i] );
		
		// if there is no next node, we add it
		if( nnod == -1 )
		{
			// we add the new edge to the graph
			graph[nod].push_back( nodi );
			// set the new node's parents
			parent[nodi] = nod;
			// set the new nodes character
			nodc[nodi] = s[i];

			// this new node will be the node we go to
			nnod = nodi;

			// increase the current number of nodes ( so the next time we know which node number to add )
			++nodi;
		}
		nod = nnod;
	}

	word[nod] = wordi;
	++wordi;
}


// calculates blue arcs ( suffix arcs ) by going to every node with a bfs
void blue( int nod )
{
	int tnod = parent[nod];// traverse nod's parent's suffixes with this
	suffix[0] = -1;// the root's sooffix has to be this so we can know that it is the root
	while( nod != 0 ) 
	{
		// we go to the next suffix
		tnod = suffix[tnod];
		// if we went past the root then we stop and the suffix will be the root
		if( tnod == -1 )
		{
			suffix[nod] = 0;
			break;
		}
		// try to find a suitable child, that can become nod's suffix
		suffix[nod] = getChild( tnod, nodc[nod] );
		// if we found one then exit the cycle
		if( suffix[nod] != -1 )
			break;
	}
	// Breadth First Search
	for( int j = 0; j < graph[nod].size(); ++j )
		blue( graph[nod][j] );
}

// same as blue but for green arcs
void green( int nod )
{
	int tnod = nod;
	while( 1 )
	{
		tnod = suffix[tnod];

		if( tnod == 0 )
		{
			dictSuffix[tnod] = 0;
			break;
		}
		if( word[tnod] )
		{
			dictSuffix[nod] = tnod;
			break;
		}

	}

	for( int j = 0; j < graph[nod].size(); ++j )
		green( graph[nod][j] );
}


ifstream fcin("ahocorasick.in");
ofstream fcout("ahocorasick.out");
int main()
{
	ios::sync_with_stdio( false );
	
	// init graph
	parent[0] = -1;
	nodc[0] = '-';
	word[0] = 0;
	suffix[0] = -1;
	dictSuffix[0] = 0;
	
	fcin >> str;	
	fcin >> n;
	for( int i = 0; i < n; ++i )
	{
		fcin >> s;
		addWord();
	}

	// make blue
	blue( 0 );
	
	// make green
	green( 0 );

	// 0 is the root of the thing
	// this is where we get the result
	int nod = 0;
	for( int i = 0; i < str.size(); ++i )
	{
		nod = nextNode( nod, str[i] );
		//cout << str[i] << " " << nod << "\n";
		// var for traversing dictionary suffixes
		int snod = nod;
		do
		{
			// except for maybe the first iteration this will always be true
			if( word[snod] )
			{
				//cout << word[snod] << "\n";
				res[word[snod]]++;
			}
			snod = dictSuffix[snod];
		}while( snod != 0 );
	}

	for( int i = 1; i <= n; ++i )
		fcout << res[i] << "\n";

	// debug stuff:
	/*/
	for( int i = 0; i < nodi; ++i )
	{
		cout << nodc[i] << " : ";
		for( int j = 0; j < graph[i].size(); ++j )
		{
			cout << nodc[graph[i][j]] << ", ";
			//cout << i << " " << graph[i][j] << "\n";
		}
		cout << "\n";
	}
	//*/
	/*/
	for( int i = 0; i < nodi; ++i )
		cout << i << " " << nodc[i] << ":  " << parent[i] << " " << nodc[parent[i]] << "\n";
	//*/
	/*/
	for( int i = 0; i < nodi; ++i )
		cout << i << " " << nodc[i] << ":  " << suffix[i] << " " << nodc[suffix[i]] << "\n";
	//*/
	/*/
	for( int i = 0; i < nodi; ++i )
		cout << i << " " << nodc[i] << ":  " << dictSuffix[i] << " " << nodc[dictSuffix[i]] << "\n";
	//*/
}