Pagini recente » Cod sursa (job #493083) | Cod sursa (job #2372152) | Cod sursa (job #1605752) | Cod sursa (job #78577) | Cod sursa (job #2899872)
/// always:
#include <cstdio>
#include <string>
/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
bool home = 1;
using namespace std;
const string TASKNAME="ahocorasick";
int n;
string s;
struct Vertex{
Vertex* kids[26];
Vertex* fail;
vector<int> inds;
int sol;
Vertex() {
for (int i=0;i<26;i++) kids[i]=nullptr;
fail=nullptr;
sol=0;
}
};
Vertex* root=new Vertex;
int sol[123];
signed main() {
#ifdef INFOARENA
home = 0;
#endif
if(!home) {
freopen((TASKNAME + ".in").c_str(), "r", stdin);
freopen((TASKNAME + ".out").c_str(), "w", stdout);
}else{
freopen ("I_am_iron_man", "r", stdin);
}
cin>>s>>n;
for (int i=1;i<=n;i++) {
string word;
cin>>word;
Vertex* current=root;
for (auto &ch:word){
int x=ch-'a';
assert(0<=x&&x<26);
if(!current->kids[x]) current->kids[x]=new Vertex;
current=current->kids[x];
}
current->inds.push_back(i);
}
vector<Vertex*> topo={root};
root->fail=root;
for (int i=0;i<(int)topo.size();i++) {
Vertex* current=topo[i];
for (int x=0;x<26;x++) {
if(current->kids[x]) {
Vertex* fail_vertex=current->fail;
while (fail_vertex!=root&&!fail_vertex->kids[x]) fail_vertex=fail_vertex->fail;
if(i>0&&fail_vertex->kids[x]) fail_vertex=fail_vertex->kids[x];
current->kids[x]->fail=fail_vertex;
topo.push_back(current->kids[x]);
}
}
}
Vertex* current=root;
for (auto &ch:s){
int x=ch-'a';
assert(0<=x&&x<26);
while (current!=root&&!current->kids[x]) current=current->fail;
if (current->kids[x]) current=current->kids[x];
current->sol++;
}
for (int i=(int)topo.size()-1;i>=0;i--) {
Vertex* current=topo[i];
current->fail->sol+=current->sol;
for (auto &i:current->inds) {
sol[i]=current->sol;
}
}
for (int i=1;i<=n;i++) {
cout<<sol[i]<<"\n";
}
/**for (auto ¤t:topo) {
cout<<current->s<<" -> "<<current->fail->s<<"\n";
}**/
}