Pagini recente » Cod sursa (job #1119481) | Cod sursa (job #2585579) | Cod sursa (job #2601760) | Cod sursa (job #1786667) | Cod sursa (job #2188542)
#include <bits/stdc++.h>
#define Nmax 101
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
int n,rez[Nmax];
string S,c;
struct trie {
trie *in[26],*fail;
vector<int> P;
int val;
trie() {
val = 0;
memset(in,0,sizeof(in));
fail = NULL;
}
}*T;
vector<trie*> C;
void add(int poz) {
trie *nod = T;
for (int i=0;i<c.size();i++) {
if (nod->in[c[i]-'a']==NULL)
nod->in[c[i]-'a'] = new trie();
nod = nod->in[c[i]-'a'];
}
nod->P.push_back(poz);
}
void bfs() {
C.push_back(T);
T->fail = T;
for (int k=0;k<C.size();k++) {
for (int i=0;i<26;i++)
if (C[k]->in[i]!=NULL) {
trie *nod = C[k]->fail;
while (nod->in[i]==NULL && nod!=T)
nod = nod->fail;
if (nod->in[i]!=NULL && nod->in[i]!=C[k]->in[i])
nod = nod->in[i];
C[k]->in[i]->fail = nod;
C.push_back(C[k]->in[i]);
}
}
}
void bfs2() {
for (int i=C.size()-1;i>=0;i--) {
C[i]->fail->val += C[i]->val;
for (int j=0;j<C[i]->P.size();j++)
rez[C[i]->P[j]] += C[i]->val;
}
}
int main()
{
T = new trie();
in>>S;
in>>n;
for (int i=1;i<=n;i++) {
in>>c;
add(i);
}
bfs();
trie *nod = T;
for (int i=0;i<S.size();i++) {
while (nod->in[S[i]-'a']==NULL && nod!=T)
nod = nod->fail;
if (nod->in[S[i]-'a']!=NULL)
nod = nod->in[S[i]-'a'];
nod->val++;
}
bfs2();
for (int i=1;i<=n;i++)
out<<rez[i]<<'\n';
in.close();
out.close();
return 0;
}