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

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.

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.

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

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

2
qwertyuiopasdfghjklzxcvbnm
qwezrtyuiopasdfghjklzxcvbnmer

Try this

2
mississipi
misisspi

   My answers are:
ert
ez
   Or
ert
me

Edited by author 11.08.2022 18:28