Pagini recente » Cod sursa (job #3167645) | Cod sursa (job #243592) | Cod sursa (job #1338961) | Cod sursa (job #1857066) | Cod sursa (job #1761870)
///Try II
#include <bits/stdc++.h>
using namespace std;
const int SIGM = 26;
ifstream fi("ahocorasick.in");
ofstream fo("ahocorasick.out");
struct Aho {
Aho *tr[SIGM], *fail;
vector<int> ordbok;
int match;
inline Aho() {
memset(tr, 0x00, sizeof(tr));
match = 0;
fail = NULL;
}
};
int n, pindex;
Aho *rt;
int ant[105];
vector<Aho*> rvq;
void put(const string &pat) {
Aho *now = rt;
for(const char &ch: pat) {
if(!now->tr[ch-'a'])
now->tr[ch-'a'] = new Aho();
now = now->tr[ch-'a'];
}
now->ordbok.push_back(++pindex);
}
void bfs(void) {
queue<Aho*> q;
Aho *now, *tmp;
rt->fail = rt;
q.push(rt);
while(!q.empty()) {
now = q.front();
q.pop();
for(int i=0; i<SIGM; ++i) if(now->tr[i]) {
q.push(now->tr[i]);
rvq.push_back(now->tr[i]);
for(tmp=now->fail; tmp!=rt && !tmp->tr[i]; tmp=tmp->fail);
if(tmp->tr[i]!=NULL && tmp->tr[i]!=now->tr[i])
tmp = tmp->tr[i];
now->tr[i]->fail = tmp;
}
}
}
void sturmgewahr(const string &txt) {
Aho *now = rt;
for(const char &ch: txt) {
while(now!=rt && !now->tr[ch-'a'])
now = now->fail;
if(now->tr[ch-'a'])
now = now->tr[ch-'a'];
++ now->match;
}
}
void anti_bfs(void) {
for(int i=rvq.size()-1; i>=0; --i) {
if(rvq[i]->fail)
rvq[i]->fail->match += rvq[i]->match;
for(const auto &j: rvq[i]->ordbok)
ant[j] = rvq[i]->match;
}
}
int main(void) {
string txt, pat;
rt = new Aho();
fi >> txt >> n;
for(int i=1; i<=n; ++i) {
fi >> pat;
put(pat);
}
bfs();
sturmgewahr(txt);
anti_bfs();
for(int i=1; i<=n; ++i)
fo << ant[i] << '\n';
return 0;
}