I have been trying to solve a modification of the Longest Common Prefix problem. It is defined below.
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
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
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?