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

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

help please, I used KMP but I have TLE_5
Послано Giorgi Saghinadze (Tbilisi SU) 25 авг 2006 03:07
#include <iostream>
#include <string>
using namespace std;


long p[260000],x,i,j,k,d,l;
char t[260000],s[510000];
void prefix()
{

     p[0]=0;k=0;
     for (i=1;i<x;i++)
     {
         while ((k>0)&&(t[k]!=t[i])) k=p[k];

         if (t[k]==t[i]) k++;
         p[i]=k;

     }

}

   void solve()
   {
        k=0;d=0;
        for (i=0;i<2*x;i++)
        {
            while ((k>0)&&(t[k]!=s[i])) k=p[k];
            if (s[i]==t[k]) k++;
            if (k>=x) {d=1;break;}
        }
        l=2*x-i-1; if (l==x) l=0;
        if (d==0) cout<<-1<<endl; else cout<<l<<endl;
   }

int main()
{long l;
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
    cin>>x; cin.get();
    for (i=1;i<=x;i++)
     p[i]=0;
     gets(s);
    l=strlen(s);
     gets(t);

     strncat(s,s,l);
     l=strlen(s);
     prefix();

     solve();
    fclose(stdin); fclose(stdout);
    return 0;
}
what is wrong here?
at last got AC
Послано Giorgi Saghinadze (Tbilisi SU) 25 авг 2006 14:00
my mistake was:
k=p[k]
should be k=p[k-1]
Re: at last got AC
Послано MIM 4 мар 2012 04:14
Giorgi,you a good man))Thank you!My mistake also there))