ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1269. Антимат

Why TLE on test7?
Послано waterkid 11 апр 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.