Pagini recente » Cod sursa (job #1200221) | Cod sursa (job #2682259) | Cod sursa (job #1327725) | Cod sursa (job #1174108) | Cod sursa (job #3308245)
#include <fstream>
#include <queue>
using namespace std;
const string txt = "ahocorasick";
ifstream f(txt + ".in");
ofstream g(txt + ".out");
struct trie {
int cnt;
trie* v[30];
trie* edge;
trie() {
cnt = 0; edge = NULL;
for (int i = 0; i < 27; i++) v[i] = NULL;
}
};
trie* root; trie* cuv[105];
int n; string s;
vector<trie*> nr;
static trie* add(string x, int p, trie* nod)
{
if (p >= x.size())
return nod;
int ind = x[p] - 'a' + 1;
if (!nod -> v[ind])
nod -> v[ind] = new trie;
return add(x, p + 1, nod -> v[ind]);
}
static void bfs()
{
queue<trie*> q;
while (!q.empty()) q.pop();
q.push(root);
while (!q.empty())
{
auto nod = q.front(); q.pop();
nr.push_back(nod);
for (int i = 1; i <= 26; i++)
if (nod -> v[i] && !nod -> v[i] -> edge)
{
auto idk = nod -> edge;
while (idk && !idk -> v[i])
idk = idk -> edge;
if (!idk) idk = root;
else idk = idk -> v[i];
nod -> v[i] -> edge = idk;
q.push(nod -> v[i]);
}
}
}
static void update()
{
while(nr.size())
{
auto nod = nr.back();
nr.pop_back();
if (nod -> edge)
nod -> edge -> cnt += nod -> cnt;
}
}
static void match()
{
trie* nod = root;
for (auto x : s)
{
int ind = x - 'a' + 1;
while (nod && !nod -> v[ind])
nod = nod -> edge;
if (!nod) nod = root;
else nod = nod -> v[ind];
nod -> cnt++;
}
}
int main()
{
f >> s >> n;
root = new trie;
for (int i = 1; i <= n; i++)
{
string x; f >> x;
cuv[i] = add(x, 0, root);
}
bfs();
match();
update();
for (int i = 1; i <= n; i++)
g << cuv[i] -> cnt << '\n';
return 0;
}