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.
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
Editorial