Monk and String Search
Tag(s):

## Binary Search, Hashing, Medium, Set, String Algorithms

Problem
Editorial
Analytics

Micro has an array A having N strings made of lower case English alphabets. He is interested in finding out the length of the longest string that occurs as a substring among all the strings in A.

Now as you know strings hate Micro, so he asked Monk for help. Since Monk is busy organizing Code Monk, he assigned this task to you.

Input:
First line consists of a single integer denoting N.
Each of the following N lines consists of a single string made of lower case English alphabets.

Output:
Print the length of the longest common substring among all strings in A.

Constraints:

$1 \le N \le 10^6$

$1 \le |A[i]| \le 10^6$

The sum of lengths of all Strings in A shall not exceed $10^6$

SAMPLE INPUT
3
abcd
bcd
cdab

SAMPLE OUTPUT
2

Explanation

String "cd" is the longest string that occurs as a substring in all the strings of array.

Time Limit: 2.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, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Code Monk (Hashing)

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Hash Tables
• Data Structures > Hash Tables
• Data Structures > Hash Tables
• Algorithms > String Algorithms