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;
}

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