Pagini recente » Cod sursa (job #784625) | Cod sursa (job #1937730) | Cod sursa (job #2942395) | Cod sursa (job #859866) | Cod sursa (job #2919933)
#include <bits/stdc++.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 f[26];
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.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];
for(auto it : automaton[automaton[pi]->_goto[ch]]->occ)
automaton[automaton[state]->_goto[ch]]->occ.push_back(it);
}
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'];
vector <int> &aux = automaton[curstate]->occ;
int z = aux.size();
for(int i = 0; i < z; i++)
res[aux[i]]++;
}
for(i = 0; i < n; i++)
printf("%d\n", res[i]);
return 0;
}