Longest Spanning Substrings solution codechef

Longest Spanning Substrings solution codechef

You are given NN strings S1,S2,,SNS1,S2,…,SN. Consider a complete undirected graph with NN vertices (numbered 11 through NN), in which the weight of an edge between vertices uu and vv is equal to the length of the longest common substring of SuSu and SvSv.

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

Input Format Longest Spanning Substrings solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • NN lines follow. For each valid ii, the ii-th of these lines contains a single string SiSi.

Output Format

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

Constraints Longest Spanning Substrings solution codechef

  • 1T1001≤T≤100
  • 1N1001≤N≤100
  • for each valid iiSiSi contains only lowercase English letters
  • the sum of lengths of all strings over all test cases does not exceed 51055⋅105

Subtasks

Subtask #1 (10 points): the sum of lengths of all strings over all test cases does not exceed 51025⋅102

Subtask #2 (20 points): the sum of lengths of all strings over all test cases does not exceed 51035⋅103

Subtask #3 (70 points): original constraints

Sample Input 1  Longest Spanning Substrings solution codechef 

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

Sample Output 1  Longest Spanning Substrings solution codechef 

4
4
2

Explanation Longest Spanning Substrings solution codechef

Example case 1: The strings S2,S3S2,S3 have a longest common substring with length 22, and the strings S1,S2S1,S2 have a longest common substring with length 11. The spanning tree which contains the edges (2,3)(2,3) and (1,2)(1,2) has the maximum weight 33.

Leave a Comment