ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1269. Obscene Words Filter

Why TLE on test7?
Posted by waterkid 11 Apr 2012 08:28
const
        maxn=100000;
var
        st,en,n,i,j,k,now,tot,m,tmp,o,ans:longint;
        s:ansistring;
        r,d,failed,fa,h:array[0..maxn]of longint;
        w:array[1..maxn,1..2]of longint;
        target:array[0..maxn]of boolean;
function min(x,y:longint):longint;
begin
        if x<y then exit(x) else exit(y);
end;
begin
        readln(n);
        for n:=1 to n do begin
                readln(s);
                now:=0;
                for j:=1 to length(s) do begin
                        i:=r[now];
                        while i<>0 do begin
                                if w[i,1]=ord(s[j]) then begin
                                        now:=i;
                                        break;
                                end;
                                i:=w[i,2];
                        end;
                        if i=0 then begin
                                inc(tot);
                                fa[tot]:=now;
                                w[tot,1]:=ord(s[j]);
                                w[tot,2]:=r[now];
                                r[now]:=tot;
                                h[tot]:=h[now]+1;
                                now:=tot;
                        end;
                end;
                target[now]:=true;
        end;
        st:=0;
        d[1]:=0;
        en:=1;
        repeat
                inc(st);
                i:=r[d[st]];
                while i<>0 do begin
                        inc(en);
                        d[en]:=i;
                        i:=w[i,2];
                end;
        until st=en;
        for j:=2 to en do begin
                k:=fa[d[j]];
                i:=0;
                while (i=0)and(k<>0) do begin
                        k:=failed[k];
                        i:=r[k];
                        while i<>0 do begin
                                if w[i,1]=w[d[j],1] then break;
                                i:=w[i,2];
                        end;
                end;
                failed[d[j]]:=i;
                if target[i] then begin
                        if not target[d[j]] then h[d[j]]:=min(h[d[j]],h[i]);
                        target[d[j]]:=target[d[j]] or target[i];
                end;
        end;
        failed[0]:=-1;
        readln(m);
        for m:=1 to m do begin
                readln(s);
                ans:=length(s)+1;
                now:=0;
                for j:=1 to length(s) do begin
                        k:=now;
                        i:=0;
                        while (i=0)and(k<>-1) do begin
                                i:=r[k];
                                while i<>0 do begin
                                        if w[i,1]=ord(s[j]) then break;
                                        i:=w[i,2];
                                end;
                                if i=0 then k:=failed[k];
                        end;
                        now:=i;
                        if target[now] then ans:=min(ans,j-h[now]+1);
                end;
                if ans<length(s) then break;
        end;
        if ans<=length(s) then begin
                writeln(m,' ',ans);
        end else writeln('Passed');
end.