Pagini recente » Cod sursa (job #1280754) | Cod sursa (job #1741083) | Cod sursa (job #1278434) | Cod sursa (job #2569141) | Cod sursa (job #2022465)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
const int MAXN = 100, ALPHALEN = 26;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
vector <string> words;
string text;
int n;
int ans[MAXN+1];
void read()
{
in>>text;
in>>n;
for(int i = 0; i < n; i++)
{
string buff;
in>>buff;
words.push_back(buff);
}
}
struct node
{
node* fail;
vector <int> output;
node* next[ALPHALEN];
int index;
node()
{
fail = NULL;
for(int i = 0; i < ALPHALEN; i++)
next[i] = NULL;
}
};
struct finiteAutomata
{
node* root;
int numStates;
finiteAutomata()
{
root = new node;
root->index = 0;
numStates = 0;
}
void addWord(node* &root,string subS,string s)
{
if(root == NULL)
{
root = new node;
numStates++;
root->index = numStates;
//cout<<"New state created"<<' '<<subS<<' '<<s<<endl;
}
if(subS.size() == 1)
{
int k = 0;
for(string word: words)
if(word != s)
k++;
else
break;
for(int word: root->output)
if(word == k)
return;
root->output.push_back(k);
return;
}
addWord(root->next[subS[0]-'a'],subS.erase(0,1),s);
}
void buildTrie(vector <string> &v)
{
for(int i = 0; i < v.size(); i++)
addWord(root->next[v[i][0]-'a'],v[i],v[i]);
}
void buildFailFunction()
{
queue <node*> Q;
for(int i = 0; i < ALPHALEN; i++)
if(root->next[i] != NULL)
{
root->next[i]->fail = root;
Q.push(root->next[i]);
//printf("fail(%d) = %d\n",root->next[i]->index,0);
}
while(Q.empty() == false)
{
node* curr = Q.front();
Q.pop();
for(int i = 0; i < ALPHALEN; i++)
if(curr->next[i] != NULL)
{
node* state = curr->fail;
while(state != NULL && state->next[i] == NULL)
state = state->fail;
if(state != NULL)
{
curr->next[i]->fail = state->next[i];
//printf("fail(%d) = %d\n",curr->next[i]->index,state->next[i]->index);
node* s = curr->next[i];
node* fs = state->next[i];
for(int i = 0; i < fs->output.size(); i++)
s->output.push_back(fs->output[i]);
}
else
{
curr->next[i]->fail = root;
//printf("fail(%d) = %d\n",curr->next[i]->index,0);
}
Q.push(curr->next[i]);
}
}
}
void matchText(string &text)
{
node* state = root;
for(int i = 0; i < text.size(); i++)
{
char currChar = text[i];
while(state != NULL && state->next[currChar-'a'] == NULL)
state = state->fail;
if(state != NULL)
{
state = state->next[currChar-'a'];
if(state->output.empty() == false)
{
for(int out: state->output)
{
ans[out]++;
}
}
}
else
state = root;
}
}
void afis(node* root)
{
if(root == NULL)
return;
if(root->output.empty() == false)
{
for(int i = 0; i < root->output.size(); i++)
cout<<root->output[i]<<endl;
}
for(int i = 0; i < ALPHALEN; i++)
afis(root->next[i]);
}
};
int main()
{
finiteAutomata T;
read();
T.buildTrie(words);
//T.afis(T.root);
//cout<<"Number of states is: "<<T.numStates<<endl;
T.buildFailFunction();
T.matchText(text);
for(int i = 0; i < n; i++)
{
bool found = false;
for(int j = 0; j < i; j++)
if(words[i] == words[j])
{
out<<ans[j]<<endl;
found = true;
break;
}
if(found == false)
out<<ans[i]<<endl;
}
return 0;
}