Solution to helium2013 (Find-Three) by codility

17 Mar

Question: https://codility.com/demo/take-sample-test/find_three

Question Name: helium2013 or Find-Three or FindThree

For this question, we have two similar but different ways to solve it. The first solution uses the border array algorithm. And the other one is with the Z algorithm for the longest common prefix. After getting the border array or prefix array, the left work seems quite similar. We try every possible border, with length being equal to or less than one third of the original string’s length, from the longest to the shortest. If we find a non-overlapping occurrence of the trying border in the middle, we return the length of that border as the final result.

The solution with border array is:

I made much less comments on the solution with Z algorithm. If you really fully understand the first solution, you could easily understand this one without any comment. But if you are still confused by the first one, the comments are unhelpful in the second solution. The solution with Z algorithm is:

Leave a Reply

Your email address will not be published. Required fields are marked *