Pagini recente » Cod sursa (job #2444251) | Cod sursa (job #1055190) | Cod sursa (job #2188598) | Cod sursa (job #1126337) | Cod sursa (job #2765213)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("ahocorasick.in");
ofstream out("ahocorasick.out");
class ahoCorasick{
public:
struct aCNode{
aCNode * nxt[26], * backRef;
int nrMch;
aCNode(){
fill(nxt, nxt+26, nullptr);
backRef = nullptr;
nrMch = 0;
}
};
ahoCorasick(){
root = new aCNode();
}
aCNode * addString(const string & s){
aCNode * nod = root;
for(auto &x: s){
if(nod->nxt[x-'a']==nullptr)
nod->nxt[x-'a']=new aCNode();
nod=nod->nxt[x-'a'];
}
return nod;
}
void buildAutomata(){
queue <pair<aCNode *, char> > q;
root->backRef = root;
for(char i=0; i<26; i++)
if(root->nxt[i]!=nullptr)
q.push({root, i});
else
root->nxt[i]=root;
vecS.push_back(root);
while(!q.empty()){
pair<aCNode *, char> per=q.front();
q.pop();
aCNode * nNow=per.first->nxt[per.second];
nNow->backRef = (per.first==root ? root : per.first->backRef->nxt[per.second]);
vecS.push_back(nNow);
for(char i=0; i<26; i++)
if(nNow->nxt[i]!=nullptr)
q.push({nNow, i});
else
nNow->nxt[i] = nNow->backRef->nxt[i];
}
}
void eatString(string & s){
aCNode * node = root;
for(auto &x:s)
node = node->nxt[x-'a'], node->nrMch++;
for(int i=vecS.size()-1; i>0; i--)
vecS[i]->backRef->nrMch+=vecS[i]->nrMch;
}
private:
aCNode * root;
vector <aCNode *> vecS;
};
ahoCorasick::aCNode * a[102];
int main()
{
string s;
in>>s;
int n;
in>>n;
ahoCorasick arb;
for(int i=1; i<=n; i++){
string p;
in>>p;
a[i] = arb.addString(p);
}
arb.buildAutomata();
arb.eatString(s);
for(int i=1; i<=n; i++)
out<<a[i]->nrMch<<"\n";
return 0;
}