Nakochi's blog

Help Needed! CC March Challenge Suffix Array WA Mistery.

By Nakochi, 10 years ago, In English

Hello everyone! I need help in this problem!

LINK to the problem.

There are two strings s and t. Find the longest string which is a substring of s and t. If there are many solutions print the first one appear in the string t.

I am one of the coders who use suffix array to solve this problem but got WAs. And the editorial to this question mentioned two ways to solve the problem without suffix array. And it's really annoying that I still don't get why my code was wrong after read the DISCUSS about this.

Please help me! Can you challenge my code?

I'd like to explain my solution first so that you can come up with some test cases that my code will fail.First as the typical suffix array's solution will do, I calculate the suffix array and lcp array of the connected string which is sa[] and hg[] in my code. Then I use binary search to get the length of the answer and get the position in the mean time. And each time check if there's a substring whose length is bigger or equal to the number we check right now. During this I separate the array of lcp into many groups each is a group consists of continued hg[i] which is bigger or equal to the number wo check right now. And if there is a group in which there is a sa[i] < ls and another sa[j] > ls, then the number we check right now is OK. (Ps, ls is the length of the first string.)This solution work in O(nlogn) I think.

Here is my code.

Is there any mistake? Please enlighten me. Thanks a lot.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

if (min(sa[i], sa[i - 1]) < ls && max(sa[i], sa[i - 1]) > ls && hg[i] >= mm) { This is the problem. Imagine what happens when you have lots of suffixes from the second string and then lots of suffixes from the first one. min(sa[i], sa[i - 1]) < ls && max(sa[i], sa[i - 1]) > ls must not necessarily be true for every position, just once for the whole group. I first computed mm and then for every group of suffixes [i, j] which have suffixes from both strings I took the minimum of the positions from the second string.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, my mistake! Sorry I post my old version code, which got AC before the test data updated. And I knew what's wrong with that solution. Anyway thanks! And I'll update my last submission code which uses binary search in a minute.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have changed the link to my solution. You can check it now. And thanks for help.

    Let me explain my idea my precisely. Take this test cases in the discuss for example.

    s and t are:

    babaazzzzyy badyybac

    And sa[] will be:

    11 3 1 18 13 4 2 0 17 12 19 14 10 16 9 15 8 7 6 5

    hg[] will be:

    0 1 1 1 1 0 2 2 2 0 0 0 1 1 2 0 1 2 3

    when I use binary search to check number 2, I will separate the hg[] into these groups:

    2 2 2

    2

    2 3

    others are ingored.

    And I will get the right answer. And also this case can explain why my old version code fail the system test. Thank you again.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      You check the suffixes only when hg[i] < x. You might miss some cases where you never reach that condition for a group. For example, this case:

      a
a
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Aha, Accepted! Your test case really helped! Emm... In fact I check the suffixes when hg[i] >= x, however I didn't check the last group hg[i] which is >= x. Because I forget to update en to n — 1. And Thank you sincerely. It seems I should be much more careful and patient to check my code one more time before I post the Help Needed Post.

        → Reply