Обсуждение @ 1713. Ключевые подстроки @ Timus Online Judge

andrei parvu WA test 2 [7] // Задача 1713. Ключевые подстроки 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

VC15 (Orel STU) Re: WA test 2 [5] // Задача 1713. Ключевые подстроки 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.

VC15 (Orel STU) Strange AC // Задача 1713. Ключевые подстроки 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.

caiweiwenjs Re: WA test 2 [3] // Задача 1713. Ключевые подстроки 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

VC15 (Orel STU) Re: WA test 2 [2] // Задача 1713. Ключевые подстроки 30 июн 2012 13:29

Yes, it could be. In this case I don't change the answer for the word.

Toshpulatov (MSU Tashkent) Re: WA test 2 [1] // Задача 1713. Ключевые подстроки 27 мар 2020 11:04

2
qwertyuiopasdfghjklzxcvbnm
qwezrtyuiopasdfghjklzxcvbnmer

NoLyrics Re: WA test 2 // Задача 1713. Ключевые подстроки 11 авг 2022 17:25

My answers are:
ert
ez
Or
ert
me

Edited by author 11.08.2022 18:28

NoLyrics Re: WA test 2 // Задача 1713. Ключевые подстроки 4 авг 2022 23:39

Try this

2
mississipi
misisspi

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