Pagini recente » Cod sursa (job #2366227) | Cod sursa (job #905173) | Cod sursa (job #528013) | Cod sursa (job #298542) | Cod sursa (job #3273761)
#pragma GCC optimize("O3, unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 55;
const int sigma = 26;
struct AhoCorasick
{
AhoCorasick *trie[sigma] = {}, *prev = NULL;
int cur = 0;
}*frev = new AhoCorasick, *location[1000005], *coada[1000005];
AhoCorasick *inser(const char sir[])
{
AhoCorasick *nod = frev;
for(int i = 0; sir[i]; nod = nod->trie[sir[i++] - 'a'])
{
if(!nod->trie[sir[i] - 'a'])
nod->trie[sir[i] - 'a'] = new AhoCorasick;
}
return nod;
}
void solve(const char sir[])
{
int st = 1, dr = 0;
frev->prev = frev;
for(coada[++dr] = frev; st <= dr; st++)
{
AhoCorasick *nod = coada[st];
for(int i = 0; i < sigma; ++i)
{
if(nod->trie[i])
{
AhoCorasick * noddoi = nod->trie[i];
AhoCorasick *copie = nod->prev;
while(copie != frev && !copie->trie[i])
copie = copie->prev;
if(copie->trie[i] && copie->trie[i] != noddoi)
noddoi->prev = copie->trie[i];
else
noddoi->prev = copie;
coada[++dr] = noddoi;
}
}
}
AhoCorasick *nod = frev;
for(int i = 0; sir[i]; ++i)
{
while(nod != frev && !nod->trie[sir[i] - 'a'])
nod = nod->prev;
if(nod->trie[sir[i] - 'a'])
nod = nod->trie[sir[i] - 'a'];
nod->cur++;
}
for(int i = dr; i > 0; --i)
if(coada[i]->prev)
coada[i]->prev->cur += coada[i]->cur;
}
int tests;
char sir[1000005];
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int32_t main(int argc, char * argv[])
{
fin >> sir;
fin.get();
fin >> tests;
for(int i = 1; i <= tests; ++i)
{
char st[10005];
fin >> st;
location[i] =inser(st);
}
solve(sir);
for(int i = 1; i <= tests; ++i)
fout << location[i]->cur << '\n';
return 0;
}