Pagini recente » Cod sursa (job #2340610) | Cod sursa (job #470361) | Cod sursa (job #38473) | Cod sursa (job #2935415) | Cod sursa (job #2333512)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream si("ahocorasick.in");
ofstream so("ahocorasick.out");
int sol[105];
string s,c;
struct trie {
trie *f[26],*fail;
int val;
vector<int> poz;
trie() {
memset(f,0,sizeof(f));
fail = NULL;
val = 0;
}
}*t;
inline void add(int x) {
trie *nod=t;
for(int i=0; i<c.size(); ++i) {
if(nod->f[c[i]-'a']==NULL) {
nod->f[c[i]-'a']=new trie();
}
nod=nod->f[c[i]-'a'];
}
nod->poz.push_back(x);
}
vector<trie*> v;
inline void bfs() {
trie *nod;
v.push_back(t);
t->fail=t;
for(int i=0; i<v.size(); ++i) {
for(int j=0; j<26; ++j) {
if(v[i]->f[j]!=NULL) {
nod=v[i]->fail;
while(nod->f[j]==NULL&&nod!=t) {
nod=nod->fail;
}
if(nod->f[j]!=NULL&&nod->f[j]!=v[i]->f[j]) {
nod=nod->f[j];
}
v[i]->f[j]->fail=nod;
v.push_back(v[i]->f[j]);
}
}
}
}
inline void bfs2() {
for(int i=v.size()-1; i>=0; --i) {
if(v[i]->fail!=NULL) {
v[i]->fail->val+=v[i]->val;
}
for(int j=0; j<v[i]->poz.size(); ++j) {
sol[v[i]->poz[j]]+=v[i]->val;
}
}
}
int main() {
int n;
si>>s;
si>>n;
t=new trie();
for(int i=1; i<=n; ++i) {
si>>c;
add(i);
}
bfs();
trie *nod=t;
for(int i=0; i<s.size(); ++i) {
while(nod->f[s[i]-'a']==NULL&&nod!=t) {
nod=nod->fail;
}
if(nod->f[s[i]-'a']!=NULL)
nod=nod->f[s[i]-'a'];
nod->val++;
}
bfs2();
for(int i=1; i<=n; ++i)
so<<sol[i]<<'\n';
return 0;
}