Pagini recente » Cod sursa (job #1656083) | Cod sursa (job #1885706) | Cod sursa (job #520812) | Cod sursa (job #3170066) | Cod sursa (job #2919879)
#include <bits/stdc++.h>
#define MAXLG 1000000
/// TONI BO$$ was here
/// #MLC
using namespace std;
vector <string> arr;
map <int,int> _goto[MAXLG + 1];
int fail[MAXLG + 1];
map <int,int> occ[MAXLG + 1];
int nostates;
int res[101];
int main()
{
int n, i, j, curstate;
string s;
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
cin >> s;
cin >> n;
for(i = 0; i < n; i++)
{
string aux;
cin >> aux;
arr.push_back(aux);
}
/*nostates = 1;
for(i = 0; i < n; i++)
{
string &word = arr[i];
int curstate = 0;
for(j = 0; j < word.size(); j++)
{
map <int,int> &aux = _goto[curstate];
if(aux[word[j] - 'a'])
curstate = aux[word[j] - 'a'];
else
aux[word[j] - 'a'] = nostates++, curstate = aux[word[j] - 'a'];
}
occ[curstate][i] = 1;
}
queue < int > q;
for(i = 0; i < 26; i++)
if(_goto[0][i])
{
q.push(_goto[0][i]);
fail[_goto[0][i]] = 0;
}
while(!q.empty())
{
int state = q.front();
q.pop();
/// for(i<-0,26)...
for(int ch = 0; ch < 26; ch++)
if(_goto[state][ch])
{
int pi = fail[state];
while(pi && !_goto[pi][ch])
pi = fail[pi];
if(_goto[pi][ch])
{
fail[_goto[state][ch]] = _goto[pi][ch];
map < int, int > &mymap = occ[_goto[pi][ch]];
for(map < int, int > :: iterator it = mymap.begin(); it != mymap.end(); ++it)
occ[_goto[state][ch]][it -> first] += it -> second;
}
else
fail[_goto[state][ch]] = 0;
q.push(_goto[state][ch]);
}
}
curstate = 0;
for(auto it : s)
{
while(curstate && !_goto[curstate][it - 'a'])
curstate = fail[curstate];
if(_goto[curstate][it - 'a'])
curstate = _goto[curstate][it - 'a'];
map < int, int > &mymap = occ[curstate];
for(map < int, int > :: iterator it = mymap.begin(); it != mymap.end(); ++it)
res[it -> first] += it -> second;
}
for(i = 0; i < n; i++)
printf("%d\n", res[i]);
*/
return 0;
}