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.