Pagini recente » Cod sursa (job #1088926) | Cod sursa (job #2583833) | Cod sursa (job #3188294) | Cod sursa (job #3295581) | Cod sursa (job #2919901)
#include <bits/stdc++.h>
#define MAXLG 1000000
/// TONI BO$$ was here
/// #MLC
using namespace std;
vector <string> arr;
struct trie
{
int _goto[26], occ[100], fail;
trie ()
{
for(int i = 0; i < 26; i++)
_goto[i] = occ[i] = 0;
for(int i = 0; i < 100; i++)
occ[i] = 0;
fail = 0;
}
};
vector <trie *> automaton;
int nostates;
int res[101];
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;
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[i] = 1;
}
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];
for(int i = 0; i < n; i++)
automaton[automaton[state]->_goto[ch]]->occ[i] += automaton[automaton[pi]->_goto[ch]]->occ[i];
}
q.push(automaton[state]->_goto[ch]);
}
}
curstate = 0;
for(auto it : s)
{
while(curstate && !automaton[curstate]->_goto[it - 'a'])
curstate = automaton[curstate]->fail;
if(automaton[curstate]->_goto[it - 'a'])
curstate = automaton[curstate]->_goto[it - 'a'];
for(int i = 0; i < n; i++)
res[i] += automaton[curstate]->occ[i];
}
for(i = 0; i < n; i++)
printf("%d\n", res[i]);
return 0;
}