Shil and LCP Pairs
Practice
3.8 (15 votes)
Math
Medium
Problem
31% Success 848 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Shil came across N strings - s1 , s2 , s3 .. sN . He wants to find out total number of unordered pairs (i, j) such that LCP(si , sj) = k. You have to do thi for every k in [0, L]. Here L = max ( len(si) ) and LCP denotes longest common prefix.

INPUT:
First line consists of integer N denoting total number of strings.Next N lines consists of strings s1 , s2 , s3 .. sN.

OUTPUT:
Print L+1 integers - h0 , h1 , h2, ..., hL where hi denotes total number of pairs having LCP value i and L = max ( len(si) ).

CONTRAINTS:
1 ≤ N ≤ 105
1≤ Σ len(si) ≤ 106
Strings consists of lower case english alphabets ( 'a' - 'z' ) only.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
3 votes
Tags:
ApprovedCircuitsData StructuresMediumTries
Points:50
5 votes
Tags:
Advanced Data StructuresData StructuresMediumTries
Points:50
43 votes
Tags:
AlgorithmsData StructuresMediumMeet-in-the-middleTries