Pagini recente » Cod sursa (job #2958285) | Cod sursa (job #789808) | Cod sursa (job #2989395) | Cod sursa (job #740391) | Cod sursa (job #923659)
Cod sursa(job #923659)
#include<fstream>
#include<string.h>
#include<vector>
using namespace std;
#define max_l 26
#define max_n 10005
#define MAX_L 1000010
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int i , p , u , n , Sol[max_n];
char A[MAX_L] , s[max_n];
struct ac{
int nr;
vector<int> L;
ac *nd[max_l];
ac *fail;
ac(){
nr = 0;
fail = NULL;
memset(nd , 0 , sizeof(nd));
}
}*T , *q[max_n*102] , *nod , *nod1;
void insert(ac *T , char *s , int nr){
if((*s) > 'z' || (*s) < 'a'){
T->L.push_back(nr);
}
else{
int urm = (*s) - 'a';
if(0==T->nd[urm])
T->nd[urm] = new ac;
insert(T->nd[urm] , s+1 , nr);
}
}
void read(){
f>>A;
f>>n;
for(int i=1;i<=n;i++){
f>>s;
insert(T , s , i);
}
}
void bfs(){
p = 1 , u = 1;
T->fail = T; q[1] = T;
while(p <= u){
nod = q[p];
for(i = 0 ; i<max_l ; i++){
if(nod->nd[i]!=0){
nod1 = nod->fail;
while(nod1 != T && nod1->nd[i] == NULL)
nod1 = nod1->fail;
if(nod1->nd[i]!=NULL && nod1->nd[i] != nod->nd[i]){
nod1 = nod1->nd[i];
}
nod->nd[i]->fail = nod1;
q[++u] = nod->nd[i];
}
}
p++;
}
}
void solve(){
int lungime = strlen(A);
int urm ;
ac *p = T;
for(int i=0;i<lungime;i++){
urm = A[i] - 'a';
while(p!=T && p->nd[urm] == NULL)
p = p->fail;
if(p->nd[urm] != NULL)
p = p->nd[urm];
p->nr++;
}
}
void antibfs(){
int j;
for(int i=u;i>0;i--){
nod = q[i];
if(nod->fail != NULL)
nod->fail->nr += nod->nr;
for(j = 0 ; j < nod->L.size() ; j++){
Sol[ nod->L[j] ] = nod->nr;
}
}
}
void print(){
for(int i = 1 ; i <= n ; i++)
g<<Sol[i]<<"\n";
}
int main(){
T = new ac;
read();
bfs();
solve();
antibfs();
print();
return 0;
}