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

Обсуждение задачи 1713. Ключевые подстроки

WA test 2
Послано andrei parvu 16 сен 2010 22:39
Can somebody tell me how they passed test nr. 2 (or give me some good test cases)?

I have a solution in O(N*M*log(N*M)) using suffix array and I can't find the bug.

Thanks

Edited by author 16.09.2010 22:39
Re: WA test 2
Послано VC15 (Orel STU) 25 июн 2012 18:40
I've got absolutely the same problem. I use suffix and lcp arrays.

I use the following algo:
for i = 1 to LENGTH_OF_ALL_WORDS
  l = the closest preceding suffix that belong to another word
  r = the closest succeeding suffix that belong to another word
  v = max(lcp(l, i), lcp(i, r)) + 1;
  w = the word that contains suffix i;
  if (v < ans[w]) ans[w] = v;

I've tried lots of tests but can't find what's wrong.
Strange AC
Послано VC15 (Orel STU) 26 июн 2012 16:39
There is something strange with this problem. I hasn't written suffix array building on my own, I used a reference implementation. Looking for a bug I replaced it with code that builds suffix array in the naive way (i.e. literally sorting suffixes). I got AC!
So there are 2 results:
- The reference implementation I used is wrong :)
- The test data seems to be weak because naive suffix and LCP arrays building gets AC.
Re: WA test 2
Послано caiweiwenjs 29 июн 2012 13:46
TO VC15 (Orel STU)
max(lcp(l, i), lcp(i, r)) + 1 may longer than the word‘s length

Edited by author 29.06.2012 13:49
Re: WA test 2
Послано VC15 (Orel STU) 30 июн 2012 13:29
Yes, it could be. In this case I don't change the answer for the word.
Re: WA test 2
Послано Toshpulatov (MSU Tashkent) 27 мар 2020 11:04
2
qwertyuiopasdfghjklzxcvbnm
qwezrtyuiopasdfghjklzxcvbnmer
Re: WA test 2
Послано NoLyrics 4 авг 2022 23:39
Try this

2
mississipi
misisspi
Re: WA test 2
Послано NoLyrics 11 авг 2022 17:25
   My answers are:
ert
ez
   Or
ert
me

Edited by author 11.08.2022 18:28