Pagini recente » Cod sursa (job #3224653) | Cod sursa (job #1857157) | Cod sursa (job #3258241) | Cod sursa (job #3274887) | Cod sursa (job #2137240)
//#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define NMax 101
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
string word[NMax];
struct Node{
Node * next[26];
Node * go[26];
Node * link;
Node * dad;
char lastChar;
int occ;
Node(Node * _dad, char _lastChar){
dad = _dad,
lastChar = _lastChar,
link = NULL,
memset(next,0,sizeof(next)),
memset(go, 0 ,sizeof(go)), occ = 0;
}
} * Root;
void Add(string s){
Node * node = Root;
for(auto it : s){
if(!node->next[it-'a']) node->next[it-'a'] = new Node(node, it);
node = node->next[it-'a'];
}
}
Node * GetLink(Node * node);
Node * go(Node * node, char c){
if(node->go[c-'a']) return node->go[c-'a'];
if(node->next[c-'a']) return node->go[c-'a'] = node->next[c-'a'];
if(node == Root) return node->go[c-'a'] = Root;
return node->go[c-'a'] = go(GetLink(node),c);
}
Node * GetLink(Node * node){
if(node->link) return node->link;
if(node == Root || node->dad == Root) return node->link = Root;
return node->link = go(GetLink(node->dad), node->lastChar);
}
void LinkDfs(Node * node){
GetLink(node);
for(int i = 0;i<26;i++)
if(node->next[i]) LinkDfs(node->next[i]);
}
void Propagate(){
vector<Node*> que;
que.push_back(Root);
int act = 0;
while(act < que.size()){
for(int i = 0;i<26;i++)
if(que[act]->next[i]) que.push_back(que[act]->next[i]);
act++;
}
for(int i = que.size()-1;i>=0;i--)
que[i]->link->occ += que[i]->occ;
}
int Get(string s){
Node * node = Root;
for(auto it:s)
node = node->next[it-'a'];
return node->occ;
}
int main() {
Root = new Node(NULL, NULL);
string str;
int n;
cin>>str;
cin>>n;
for(int i=1;i<=n;i++){
cin>>word[i];
Add(word[i]);
}
LinkDfs(Root);
Node * node = Root;
for(auto it : str){
node = go(node, it);
node->occ++;
}
Propagate();
for(int i=1;i<=n;i++)
cout<<Get(word[i])<<'\n';
return 0;
}