Fun with strings

★★★★★

2 votes

Arrays, LCP, Medium, String Manipulation, Suffix tree

Details

Problem

You are given a string $S = S_0S_1 \cdots S_{n-1}$ of length n.
Find the sum of length of LCP(Longest Common Prefix) over all the $\frac{n^2(n+1)^2}{4}$ ordered pairs of its substrings.
Formally, say the substring of S starting at index i and ending at index j is represented by $S_{ij}$ , and let $L(A,B)$ represent the length of LCP of strings A and B.
Then compute the value of :

$\displaystyle \large \sum_{i=0}^{n-1} \sum_{j=i}^{n-1} \sum_{k=0}^{n-1} \sum_{l=k}^{n-1} L(S_{ij},S_{kl})$

As this value may be very large, print it modulo 10^9 + 7

Input
The first line contains T, the number of test cases. It is followed by $2T$ lines, describing the strings in the testcases . Each string is described by two lines.
The first line contains n, length of the string S.
Second line contains the string S consisting of lowercase english alphabets only.

Output
Print T lines containing the sum of lengths of lcp over all ordered pairs of substrings of S modulo 10^9+7 for the T testcases, each on a new line.

Constraints

$T \le 5$
S consists of lowercase english alphabets only.
(25 points) : $n \le 10^3$
(75 points) : $n \le 10^5$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

When $S=ab$ , the answer equals
$L(a,a)+L(a,ab) + L(a,b) + L(ab,a)+L(ab,ab)+L(ab,b)+L(b,a)+L(b,ab)+L(b,b)$

$= 1+1+0+1+2+0+0+0+1 = 6$