### D_Coder_03's blog

By D_Coder_03, history, 16 months ago, 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(A_i)) 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  Comments (6)
 » 16 months ago, # | ← Rev. 3 →   You can just compare the first $k$ characters of every adjacent pair of strings. So you can just remove the rest of the characters. Now let's say you got $A_i = A_{i+1} ... = A_j$, you can add $\binom{j-i+1}{2}$ to the total answer. Since each string is being compared twice at most, the time complexity is $O(\sum |A|)$. Edit : Set answer to $n$ initially.
•  » » » Let's take an example, $A = "ab", "ac", "bc"$, K=1. Let's keep only the first $k$ characters of all strings in $A$. So $A = "a", "a", "c"$. Now the consecutive ranges of equal elements are $(1,2), (3,3)$. So the answer is $n + \binom{2 - 1 + 1}{2} + \binom{3- 3 + 1}{2}$. That is because in a range of length of $l$, there are $\binom{l}{2}$ subarrays of length $>1$. We add $n$ for single length subarrays.