Return to Question

Defining substring

For a string P with characters P₁, P₂,…, P_q, let us denote by P[i, j] the substring P_{i, Pi+1,…, Pj.}

Defining longest common prefix

LCP(S₁, S₂,…, S_K), is defined as largest possible integer j such that S₁[1, j] = S₂[1, j] = … = S_K[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(A_i, A_i+1,…, A_j) ≥ K. Print required answer modulo 10⁹+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*10⁵. Strings consist of small alphabets only.

Defining substring

For a string P with characters P₁, P₂,…, P_q, let us denote by P[i, j] the substring P_i, P_i+1,…, P_j.

Defining longest common prefix

LCP(S₁, S₂,…, S_k), is defined as largest possible integer j such that S₁[1, j] = S₂[1, j] = … = S_k[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(A_i, A_i+1,…, A_j) ≥ K. Print required answer modulo 10⁹+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 

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

Constraints

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

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 10^9+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 

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

Constraints

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

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 P₁, P₂,…, P_q, let us denote by P[i, j] the substring P_{i, Pi+1,…, Pj.}

Defining longest common prefix

LCP(S₁, S₂,…, S_K), is defined as largest possible integer j such that S₁[1, j] = S₂[1, j] = … = S_K[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(A_i, A_i+1,…, A_j) ≥ K. Print required answer modulo 10⁹+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*10⁵. Strings consist of small alphabets only.

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

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