Cod sursa(job #2077922)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 28 noiembrie 2017 18:42:12
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.95 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stack>

#define greenv dictSuffix
#define bluev suffix

using namespace std;

const int NLIM = 2e6 + 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
vector< 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].push_back( wordi );
	++wordi;
}

//*/
// calculates blue arcs ( suffix arcs ) by going to every node with a bfs
void blue( int nod )
{
	stack< int > st;
	st.push( 0 );
	while( st.size() )
	{
		nod = st.top();
		st.pop();
		//cout << nod << "\n";
		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 ) 
		{
			//cout << tnod << " ";
			// 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
			//cout << tnod << " ";
			if( tnod == -1 )
			{
				//cout << "|1|  ";
				suffix[nod] = 0;
				break;
			}
			// try to find a suitable child, that can become nod's suffix
			suffix[nod] = getChild( tnod, nodc[nod] );
			//cout << suffix[nod] << " ";
			// if we found one then exit the cycle
			if( suffix[nod] != -1 )
				break;
		}
		//cout << "+\n";
		// Breadth First Search ( Actually I'm stupid and this is a depth-first search )
		for( int j = graph[nod].size() - 1; j >= 0; --j )
			st.push( graph[nod][j] );
	}
	//cout << "\n";
}
//*/


/*/
// calculates blue arcs ( suffix arcs ) by going to every node with a bfs
void blue( int nod )
{

	cout << 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 ) 
	{
		cout << tnod << " ";
		// 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
		cout << tnod << " ";
		if( tnod == -1 )
		{
			cout << "|1|  ";
			suffix[nod] = 0;
			break;
		}
		// try to find a suitable child, that can become nod's suffix
		suffix[nod] = getChild( tnod, nodc[nod] );
		cout << suffix[nod] << " ";
		// if we found one then exit the cycle
		if( suffix[nod] != -1 )
			break;
	}
	cout << "+\n";
	// Breadth First Search ( Actually I'm stupid and this is a depth-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 )
{
	stack< int > st;
	st.push( 0 );
	while( st.size() )
	{
		nod = st.top();
		st.pop();
		//cout << nod << "\n";
		int tnod = nod;
		while( 1 )
		{
			tnod = suffix[tnod];

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

		}

		for( int j = graph[nod].size() - 1; j >= 0; --j )
			st.push( 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].size() )
		{
			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] = '-';
	suffix[0] = -1;
	dictSuffix[0] = 0;
	
	fcin >> str;	
	fcin >> n;
	for( int i = 0; i < n; ++i )
	{
		fcin >> s;
		addWord();
	}
	//cout << "boii";
	// make blue
	blue( 0 );
	//cout << "do we?";
	
	// make green
	green( 0 );
	//cout << "do we2?";

	// 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
		{
			for( int j = 0; j < word[snod].size(); ++j )
			{
				//cout << word[snod][j] << "\n";
				res[word[snod][j]]++;
			}
			snod = dictSuffix[snod];
		}while( snod != 0 );
	}
	//cout << "\n";
	for( int i = 1; i <= n; ++i )
		fcout << res[i] << "\n";

	// debug stuff:
	/*/
	for( int i = 0; i < nodi; ++i )
	{
		cout <<  nodc[i] << "(" << i << ")" << " : ";
		for( int j = 0; j < graph[i].size(); ++j )
		{
			cout << nodc[graph[i][j]] << "(" << 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";
	//*/
}