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

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

WA#6 using KMP. Can anyone help me?
Послано williamljb 30 апр 2009 11:38
program p1423;
var
  p:array[0..250000]of longint;
  a,b:array[0..250000]of char;
  i,j,k,n,m:longint;
begin
  readln(n);
  for i:=1 to n do
    read(b[i]);
  readln;
  for i:=1 to n do
    read(a[i]);
  readln;
  p[1]:=0;
  j:=0;
  for i:=2 to n do
    begin
      while(j>0)and(b[j+1]<>b[i])do
        j:=p[j];
      if b[j+1]=b[i]
        then j:=j+1;
      p[i]:=j;
    end;
  j:=0;
  for i:=1 to n do
    begin
      while(j>0)and(b[j+1]<>a[i])do
        j:=p[j];
      if b[j+1]=a[i]
        then j:=j+1;
    end;
  if j=n
    then begin
      writeln(0);
      halt;
    end;
  if j<>0
    then writeln(n-j)
    else writeln(-1);
end.

Thanks for helping!
Sorry for my English...
Re: WA#6 using KMP. Can anyone help me?
Послано [LG]_#\#@P$T[101]R 30 апр 2009 14:42
read string S, read string T, S := S + S, prefix, kmp and AC :)
Re: WA#6 using KMP. Can anyone help me?
Послано Proba 29 авг 2010 16:40
s = s + s. I got AC.