Pagini recente » Cod sursa (job #1472659) | Cod sursa (job #2119521) | Cod sursa (job #2693888) | Cod sursa (job #1807811) | Cod sursa (job #2200254)
#include <bits/stdc++.h>
#define Nmax 102
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int n,ans[Nmax];
string A,c;
struct trie{
trie *f[26];
trie *next[26],*link,*T;
vector<int> cuv;
int val, lit;
trie(trie *_T,int _lit){
memset(f,0,sizeof(f));
memset(next,0,sizeof(next));
link = 0;
cuv.clear();
val = 0;
T = _T;
lit = _lit;
}
}*Root;
trie *go(trie*,int);
trie* getlink(trie *nod){
if (nod->link) return nod->link;
if (nod==Root || nod->T==Root) return nod->link = Root;
return nod->link = go(getlink(nod->T),nod->lit);
}
trie* go(trie *nod, int c){
if (nod->next[c]) return nod->next[c];
if (nod->f[c]) return nod->next[c] = nod->f[c];
if (nod == Root) return Root;
return nod->next[c] = go(getlink(nod),c);
}
void add(string s,int id){
trie *nod = Root;
for (auto it : s){
if (!nod->f[it - 'a']) nod->f[it - 'a'] = new trie(nod, it - 'a');
nod = nod->f[it-'a'];
}
nod->cuv.push_back(id);
}
int main()
{
Root = new trie(0,-2);
f>>A;
f>>n;
for (int i=1;i<=n;i++){
f>>c;
add(c,i);
}
trie *nod = Root;
for (auto it : A){
nod = go(nod,it-'a');
nod->val++;
}
vector<trie*> H;
H.push_back(Root);
for (int i=0;i<H.size();i++){
for (auto it : H[i]->f){
if (it) H.push_back(it);
}
}
for (int i=H.size()-1;i>=0;i--){
getlink(H[i])->val += H[i]->val;
for (auto C : H[i]->cuv) ans[C] += H[i]->val;
}
for (int i=1;i<=n;i++){
g<<ans[i]<<'\n';
}
return 0;
}