Pagini recente » Cod sursa (job #1947127) | Cod sursa (job #2330060) | Cod sursa (job #1795665) | Cod sursa (job #518162) | Cod sursa (job #2409702)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n, m, i;
char a[1000005], s[10005];
struct trie{
int sum, viz;
trie *f[26], *bc;
vector<trie*> w;
trie(){
sum = viz = 0;
bc = NULL;
for(int i = 0; i < 26; i++){
f[i] = NULL;
}
}
};
trie *r, *nod, *rad[105], *aux;
queue<trie*> c;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
void adauga(trie *r, char *s){
if(*s == 0){
rad[i] = r;
}
else{
if(r->f[*s - 'a'] == NULL){
r->f[*s - 'a'] = new trie;
}
adauga(r->f[*s - 'a'], s + 1);
}
}
void dfs(trie *nod){
if(nod->viz == 1){
return;
}
nod->viz = 1;
for(int i = 0; i < nod->w.size(); i++){
trie *aux = nod->w[i];
dfs(aux);
nod->sum += aux->sum;
}
}
int main(){
fin>> a + 1;
m = strlen(a + 1);
fin>> n;
r = new trie;
for(i = 1; i <= n; i++){
fin>> s;
adauga(r, s);
}
for(i = 0; i < 26; i++){
if(r->f[i] != NULL){
r->w.push_back(r->f[i]);
r->f[i]->bc = r;
c.push(r->f[i]);
}
}
while(!c.empty()){
nod = c.front();
c.pop();
for(i = 0; i < 26; i++){
if(nod->f[i] != NULL){
aux = nod->bc;
while(aux != r && aux->f[i] == NULL){
aux = aux->bc;
}
if(aux->f[i] != NULL){
nod->f[i]->bc = aux->f[i];
}
else{
nod->f[i]->bc = r;
}
nod->f[i]->bc->w.push_back(nod->f[i]);
c.push(nod->f[i]);
}
}
}
nod = r;
for(i = 1; i <= m; i++){
a[i] -= 'a';
while(nod != r && nod->f[ a[i] ] == NULL){
nod = nod->bc;
}
if(nod->f[ a[i] ] != NULL){
nod = nod->f[ a[i] ];
}
nod->sum++;
}
dfs(r);
for(i = 1; i <= n; i++){
fout<< rad[i]->sum <<"\n";
}
return 0;
}