Longest Spanning Substrings Problem Code: LNGSUBSubmit

Read problem statements in Mandarin, Bengali, Russian, and Vietnamese as well.

You are given $N$ strings $S_{1}, S_{2}, \dots, S_{N}$ . Consider a complete undirected graph with $N$ vertices (numbered $1$ through $N$ ), in which the weight of an edge between vertices $u$ and $v$ is equal to the length of the longest common substring of $S_{u}$ and $S_{v}$ .

Find the maximum possible weight of a spanning tree of this graph.

Input Format

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$ .
$N$ lines follow. For each valid $i$ , the $i$ -th of these lines contains a single string $S_{i}$ .

Output Format

For each test case, print a single line containing one integer --- the maximum weight of a spanning tree.

Constraints

$1 \leq T \leq 100$
$1 \leq N \leq 100$
for each valid $i$ , $S_{i}$ contains only lowercase English letters
the sum of lengths of all strings over all test cases does not exceed $5 \cdot 10^{5}$

Subtasks

Subtask #1 (10 points): the sum of lengths of all strings over all test cases does not exceed $5 \cdot 10^{2}$

Subtask #2 (20 points): the sum of lengths of all strings over all test cases does not exceed $5 \cdot 10^{3}$

Subtask #3 (70 points): original constraints

Sample Input 1

3
3
bbcab
aa
aab
3
bbc
bcaa
abb
3
aa
acc
abbca

Sample Output 1

4
4
2

Explanation

Example case 1: The strings $S_{2}, S_{3}$ have a longest common substring with length $2$ , and the strings $S_{1}, S_{3}$ have a longest common substring with length $2$ . The spanning tree which contains the edges $(2, 3)$ and $(1, 3)$ has the maximum weight $4$ .

Search This Blog

Code with Kianae

Longest Spanning Substrings Problem Code: LNGSUB Codechef Solutions