Pagini recente » Cod sursa (job #471894) | Cod sursa (job #1146389) | Cod sursa (job #1828020) | Cod sursa (job #1172108) | Cod sursa (job #2919951)
#include <bits/stdc++.h>
#include <sys/time.h>
#define MAXLG 1000000
/// TONI BO$$ was here
/// #MLC
using namespace std;
vector <string> arr;
struct trie
{
int _goto[26], fail;
vector <int> occ;
trie ()
{
memset(_goto, 0, sizeof(_goto));
fail = 0;
}
};
vector <trie *> automaton;
int nostates;
int res[101];
int matches[MAXLG + 1];
int main()
{
int n, i, j, curstate;
string s;
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
//trie X;
automaton.push_back(new trie);
cin >> s;
cin >> n;
for(i = 0; i < n; i++)
{
string aux;
cin >> aux;
arr.push_back(aux);
}
nostates = 1;
curstate = 0;
struct timeval start, stop, elapsed;
//gettimeofday(&start, NULL);
for(i = 0; i < n; i++)
{
string &word = arr[i];
curstate = 0;
for(j = 0; j < word.size(); j++)
{
trie * &aux = automaton[curstate];
if(aux->_goto[word[j] - 'a'])
curstate = aux->_goto[word[j] - 'a'];
else
{
curstate = nostates, aux->_goto[word[j] - 'a'] = nostates++;
automaton.push_back(new trie);
}
}
automaton[curstate]->occ.push_back(i);
}
queue < int > q;
for(i = 0; i < 26; i++)
if(automaton[0]->_goto[i])
q.push(automaton[0]->_goto[i]);
/*
*/
while(!q.empty())
{
int state = q.front();
q.pop();
/// for(i<-0,26)...
for(int ch = 0; ch < 26; ch++)
if(automaton[state]->_goto[ch])
{
int pi = automaton[state]->fail;
while(pi && !automaton[pi]->_goto[ch])
pi = automaton[pi]->fail;
if(automaton[pi]->_goto[ch])
{
automaton[automaton[state]->_goto[ch]]->fail = automaton[pi]->_goto[ch];
vector <int> &aux = automaton[automaton[pi]->_goto[ch]]->occ;
vector <int> &dest = automaton[automaton[state]->_goto[ch]]->occ;
int z = aux.size();
for(int i = 0; i < z; i++)
dest.push_back(aux[i]);
}
q.push(automaton[state]->_goto[ch]);
}
}
curstate = 0;
int m = s.size(), z;
char it;
//gettimeofday(&start, NULL);
for(int i = 0; i < m; i++)
{
it = s[i];
while(curstate && !automaton[curstate]->_goto[it - 'a'])
curstate = automaton[curstate]->fail;
if(automaton[curstate]->_goto[it - 'a'])
curstate = automaton[curstate]->_goto[it - 'a'];
matches[curstate]++;
}
/*gettimeofday(&stop, NULL);
//timersub(&stop, &start, &elapsed);
printf("Busy loop took %lu.%06lu seconds\n", start.tv_sec,
start.tv_usec);
printf("Busy loop took %lu.%06lu seconds\n", stop.tv_sec,
stop.tv_usec);*/
for(int i = 0; i < nostates; i++)
if(matches[i])
{
int k = matches[i];
vector <int> &aux = automaton[i]->occ;
z = aux.size();
for(int j = 0; j < z; j++)
res[aux[j]] += k;
}
for(i = 0; i < n; i++)
printf("%d\n", res[i]);
return 0;
}