Pagini recente » Cod sursa (job #347599) | Cod sursa (job #1332929) | Cod sursa (job #3198890) | Istoria paginii runda/oni_2005 | Cod sursa (job #1560154)
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#define BUF_SIZE 4096
#define MAXN 1000000
#define MAXM 100
#define MAXL 10000
#define SIG 26
struct node{
int nr;
struct node *fii[SIG], *fail;
node(){
nr=0;
memset(fii, 0, sizeof fii);
fail=NULL;
}
}*root, *q[MAXL*MAXM], *e[MAXM];
char a[MAXN];
int st, dr;
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
if(pos==BUF_SIZE){
fread(buf, BUF_SIZE, 1, fin);
pos=0;
}
return buf[pos++];
}
inline int read(){
int x=0;
char ch=nextch();
while(!isdigit(ch)){
ch=nextch();
}
while(isdigit(ch)){
x=10*x+ch-'0';
ch=nextch();
}
return x;
}
inline void makeFail(){
int i;
node *x;
st=0;
dr=0;
for(i=0; i<SIG; i++){
if(root->fii[i]!=NULL){
q[dr++]=root->fii[i];
root->fii[i]->fail=root;
}
}
while(st<dr){
for(i=0; i<SIG; i++){
if(q[st]->fii[i]!=NULL){
q[dr++]=q[st]->fii[i];
x=q[st]->fail;
while((x!=root)&&(x->fii[i]==NULL)){
x=x->fail;
}
if(x->fii[i]!=NULL){
q[st]->fii[i]->fail=x->fii[i];
}else{
q[st]->fii[i]->fail=root;
}
}
}
st++;
}
}
int main(){
int n, m, i;
char ch;
node *p;
FILE *fout;
fin=fopen("ahocorasick.in", "r");
fout=fopen("ahocorasick.out", "w");
root=new node();
ch=nextch();
n=0;
while(ch!='\n'){
a[n++]=ch;
ch=nextch();
}
m=read();
for(i=0; i<m; i++){
ch=nextch();
p=root;
while(ch!='\n'){
if(p->fii[ch-'a']==NULL){
p->fii[ch-'a']=new node();
}
p=p->fii[ch-'a'];
ch=nextch();
}
e[i]=p;
}
makeFail();
p=root;
for(i=0; i<n; i++){
while((p!=root)&&(p->fii[a[i]-'a']==NULL)){
p=p->fail;
}
if(p->fii[a[i]-'a']!=NULL){
p=p->fii[a[i]-'a'];
}
p->nr++;
}
for(i=dr-1; i>=0; i--){
q[i]->fail->nr+=q[i]->nr;
}
for(i=0; i<m; i++){
fprintf(fout, "%d\n", e[i]->nr);
}
fclose(fin);
fclose(fout);
return 0;
}