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

Обсуждение задачи 1423. Басня о строке

Wong answer#16! What's wrong?
Послано PanYe 11 авг 2006 09:19
Program KMP;

Const
  Maxn=250000;

Var
  i,j,n,k,l,ans:Longint;
  S,T:ansistring;
  Next:array[0..Maxn] of Longint;

Begin
  Readln(N);
  Readln(S);
  Readln(T);
  S:=S+S;
  Next[0]:=0;Next[1]:=0;k:=0;
  For i:=2 to length(T) Do
    Begin
      While (k>0) And (T[i]<>T[k+1]) Do
        K:=Next[k];
      If (T[i]=T[k+1]) Then Inc(K);
      Next[i]:=k;
    End;
  I:=1;j:=1;
  While I<=length(S) Do
    Begin
      L:=I;
      While (i<=2*n) And (j<=n) And (S[I]=T[J]) Do
        Begin
          Inc(i);Inc(J);
        End;
      Ans:=i-n;
      If J=n+1 Then Break;
      If J=1 Then I:=L+1 Else I:=L+J-1-Next[j-1];
      J:=Next[J-1]+1;
    End;
  l:=Ans;
  If n-l+1=n Then Writeln(0) Else If i>length(S) Then Writeln(-1) Else Writeln(n-l+1);
  End.
Re: Wong answer#16! What's wrong?
Послано Lomir 21 янв 2007 23:06
Solving this problem I was caught by all triky tests (WA6, WA8, WA16).

So test 16 is something like this:
6
aabaaa
aaabaa

Answer is: 1
Your program, like mine at first, would output 5, i think.