Pagini recente » Istoria paginii runda/cnitv_baraj_2 | Cod sursa (job #1297252) | Cod sursa (job #1811464) | Cod sursa (job #932151) | Cod sursa (job #2765223)
#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(){
root->backRef = root;
vecS.push_back(root);
for(char i=0; i<26; i++)
if(root->nxt[i]!=nullptr)
vecS.push_back(root->nxt[i]), root->nxt[i]->backRef=root;
else
root->nxt[i] = root;
for(int st=1; st<vecS.size(); st++){
aCNode * nNow=vecS[st];
for(char i=0; i<26; i++)
if(nNow->nxt[i]!=nullptr)
vecS.push_back(nNow->nxt[i]), nNow->nxt[i]->backRef=nNow->backRef->nxt[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;
}