Pagini recente » Cod sursa (job #1424485) | Cod sursa (job #2894877) | Cod sursa (job #1256841) | Cod sursa (job #1080951) | Cod sursa (job #1553855)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 260000 + 10;
struct trie
{
trie *nxt[26];
trie *phi;
int nr;
trie()
{
for (int i = 0 ; i < 26 ; ++i)
nxt[i] = 0;
phi = 0;
nr = 0;
}
};
trie *w[nmax] , *iq[nmax];
trie *root , *q , *x;
string s , t;
int n , p , u , i , c;
void add(trie *node , int p)
{
if (p == t.size())
{
w[i] = node;
return ;
}
int c = t[p] - 'a';
if (node -> nxt[c]) ;
else node -> nxt[c] = new trie();
add(node -> nxt[c] , p + 1);
}
int main()
{
freopen("ahocorasick.in" , "r" , stdin);
freopen("ahocorasick.out" , "w" , stdout);
cin >> s;
cin >> n;
root = new trie();
for (i = 1 ; i <= n ; ++i)
{
cin >> t;
add(root , 0);
}
p = 1 , u = 0;
for (i = 0 ; i < 26 ; ++i)
if (root -> nxt[i])
{
iq[++u] = root -> nxt[i];
root -> nxt[i] -> phi = root;
}
while (p <= u)
{
q = iq[p++];
for (c = 0 ; c < 26 ; ++c)
if (q -> nxt[c])
{
x = q -> phi;
while (x - root && !x -> nxt[c])
x = x -> phi;
if (x -> nxt[c]) x = x -> nxt[c];
q -> nxt[c] -> phi = x;
iq[++u] = q -> nxt[c];
}
}
q = root;
for (i = 0 ; i < s.size() ; ++i)
{
c = s[i] - 'a';
while (q - root && !q -> nxt[c])
q = q -> phi;
if (q -> nxt[c]) q = q -> nxt[c];
q -> nr += 1;
}
for (i = u ; i ; --i)
iq[i] -> phi -> nr += iq[i] -> nr;
for (i = 1 ; i <= n ; ++i)
cout << w[i] -> nr << '\n';
return 0;
}