ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1269. Obscene Words Filter

help with aho corasick MLE 7!
Posted by muhammad 18 Sep 2010 22:49
I can't think of a way to store goto and fail transitions of so many vertices and avoid MLE. please help.

here's code:

#include <stdio.h>
#include <queue>
using namespace std;
short g[110000][256];
short f[110000];
short o[110000];
short n,m,newstate=0;
queue<short>Q;
int main(void){
short i,pos=0,q,r,u,v,ch,state;
scanf("%hd",&n);getchar();
for(i=1;i<=n;++i){
r=0;
ch=getchar();
state=0;
++r;
ch+=128;
while(g[state][ch]){
state=g[state][ch];
ch=getchar();
++r;
ch+=128;
}
while(ch!='\n'+128){
newstate=newstate+1;
g[state][ch]=newstate;
state=newstate;
ch=getchar();
++r;
ch+=128;
}
o[state]=r-1;
}
for(i=0;i<256;++i){
if(q=g[0][i]){
f[q]=0;
Q.push(q);
}
}
while(!Q.empty()){
r=Q.front();
Q.pop();
for(i=0;i<256;++i){
u=g[r][i];
if(!(u==0&&r>0)){
Q.push(u);
v=f[r];
while(g[v][i]==0&&v>0) v=f[v];
f[u]=g[v][i];
if(o[u]==0) o[u]=o[f[u]];
}
}
}
scanf("%hd",&m);getchar();
for(i=1;i<=m;++i){
q=0;r=0;
while((ch=getchar())!='\n'){
ch+=128;
++r;
while(g[q][ch]==0&&q>0) q=f[q];
q=g[q][ch];
if(o[q]){
printf("%hd %hd",i,r-o[q]+1);
return 0;
}
}
}
printf("Passed\n");
return 0;
}
Re: help with aho corasick MLE 7!
Posted by Irakli Khomeriki 21 Sep 2018 23:02
you got pretty close, modified your solution to get AC. let me know if you need hints :) ikhomeriki@gmail.com

Edited by author 21.09.2018 23:04