I have been trying to solve a modification of the Longest Common Prefix problem. It is defined below.

Defining substring

For a string P with characters P1, P2,…, Pq, let us denote by P[i, j] the substring Pi, Pi+1,…, Pj.

Defining longest common prefix

LCP(S1, S2,…, SK), is defined as largest possible integer j such that S1[1, j] = S2[1, j] = … = SK[1, j].

You are given an array of N strings, A1, A2 ,…, AN and an integer K. Count how many indices (i, j) exist such that 1 ≤ i ≤ j ≤ N and LCP(Ai, Ai+1,…, Aj) ≥ K. Print required answer modulo 109+7.

Note that K does not exceed the length of any of the N strings. K <= min(len(Ai)) for all i

For example,

A = ["ab", "ac", "bc"] and K=1.

LCP(A[1, 1]) = LCP(A[2, 2]) = LCP(A[3, 3]) = 2
LCP(A[1, 2]) = LCP("ab", "ac") = 1
LCP(A[1, 3]) = LCP("ab", "ac", "bc") = 0
LCP(A[2, 3]) = LCP("ac", "bc") = 0

So, the answer is 4. Return your answer % MOD = 1000000007

Constraints

1 ≤ Sum of length of all strings ≤ 5*105. Strings consist of small alphabets only.

Here is my approach:

class Solution:
    # @param A : list of strings
    # @param B : integer
    # @return an integer
    def LCPrefix(self, A, B):
        res = 0
        for i in xrange(len(A)):
            prev = A[i]
            prevLCP = len(A[i])
            for j in xrange(i, len(A)):
                prevLCP = self.getLCP(prev, A[j], prevLCP) 
                prev = A[j]

                if prevLCP >= B:
                    res += 1

        return res % 1000000007

    def getLCP(self, A, B, upto):
        i = 0
        lim = min(upto, len(B))
        while i < lim:
            if A[i] != B[i]:
                break

            i += 1

        return i

The time complexity of this algorithm is O(n^2*m), where n is the length of the list and m is the maximum length of the string.

The online judge (InterviewBit) does not accept this solution in terms of time complexity. Can anyone think of a way to improve it?

  • Hint: it's possible in O(n * K) without using any fancy datastructures. – Peter Taylor Jul 26 '16 at 7:28

Note: although I hinted in a comment that there's a O(n * K) solution, I'm deliberately not going to give it to you (and I hope that by bumping the question to the front page I don't cause someone else to) because in my opinion the point of challenge websites is for you to learn by doing, and you will learn more effectively by figuring it out yourself with hints than by getting the solution on a plate. However, I do have some comments on your code.

class Solution:
    # @param A : list of strings
    # @param B : integer
    # @return an integer

It's useful to document the expected type, but it's more useful to document the meaning. Here B is the K of the problem specification, but I shouldn't have to work that out myself. The parameters would benefit from descriptive names, and the @return should outline what the integer returned means.

    def LCPrefix(self, A, B):
        res = 0
        for i in xrange(len(A)):
            prev = A[i]
            prevLCP = len(A[i])
            for j in xrange(i, len(A)):
                prevLCP = self.getLCP(prev, A[j], prevLCP) 
                prev = A[j]

There's a possible minor optimisation here: when j == i you already know the LCP, but you calculate it again. In my opinion it would be worth duplicating the simple test if prevLCP >= B: res += 1 before the loop, and only considering j > i. As a bonus, you would no longer need to track prev because you would always be testing the common prefix of A[j-1] and A[j]. (Hint: does that give you any ideas for optimisation?)

Why the update to prevLCP? I can figure it out, but a comment (and a better name - because the value of prevLCP isn't the previous LCP) would be useful.

                if prevLCP >= B:
                    res += 1

An else: break clause here would not change the asymptotic complexity of your solution, but it would surely make it much faster in many test cases.

        return res % 1000000007

I'll give you one more hint about improving the complexity: the fact that they want the answer modulo 109 is a really big clue that you shouldn't compute it solely via res += 1.

    def getLCP(self, A, B, upto):

Document the parameters, and think about the names. getLCP implies to me that the return value should be the longest common prefix: i.e. a string. But it's actually an integer, and it might not even be the length of the LCP because of upto.

        i = 0
        lim = min(upto, len(B))
        while i < lim:
            if A[i] != B[i]:
                break

            i += 1

        return i

In the other method you used xrange: why not here?

        lim = min(upto, len(B))
        for i in xrange(lim):
            if A[i] != B[i]:
                return i
        return lim
  • you could do spoiler, if you have answer give it(link, point it), or better remove that part of answer, to not provoke someone to post it (if it's really exists) – MolbOrg Jul 28 '16 at 11:17

My guess is that you will want to use a DAWG or similar structure. This will take a while to start, but it will greatly speed up prefix searches.

  • 3
    While a recommendation for a new way is always great, it isn't really a review. Please either review the code, optionally including this recommendation, or leave this recommendation as a comment on the question and delete this answer. – zondo Jul 27 '16 at 0:16

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.