All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Shil and LCP Pairs
Tag(s):

Mathematics, Medium-Hard

Problem
Editorial
Analytics

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.

SAMPLE INPUT
5
aaaa
ab
abcd
aaae
g
SAMPLE OUTPUT
4 4 1 1 0 
Explanation

All the pairs having LCP 0 are (1,5) , (2,5) , (3,5) , (4,5)
All the pairs having LCP 1 are (1,2) , (1,3) , (2,4) , (3,4)
All the pairs having LCP 3 are (1,4)
All the pairs having LCP 2 are (2, 3)

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Tries/Suffix Tree)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?