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 iFor example,A = [ab, ac, bc] and K=1.LCP(A[1, 1]) = LCP(A[2, 2]) = LCP(A[3, 3]) = 2LCP(A[1, 2]) = LCP(ab, ac) = 1LCP(A[1, 3]) = LCP(ab, ac, bc) = 0LCP(A[2, 3]) = LCP(ac, bc) = 0So, the answer is 4. Return your answer % MOD = 1000000007Constraints1  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 iThe 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?
Finding longest common prefix
python;algorithm;strings;programming challenge;time limit exceeded