Pagini recente » Cod sursa (job #1712972) | Cod sursa (job #1611074) | Cod sursa (job #2760764) | Cod sursa (job #165844) | Cod sursa (job #2077841)
#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";
//*/
}