0.SW. Longest Common Substring of n Strings


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

A string P is call substring of the string S if P is a sequence that appears in the same order and necessarily contiguous in the string S.

Given n string sequences S1; S2; : : : ; Sn, your task is to write a program to ?nd the length of longest substring present in all of them.

Input

The input ?le contains n lines, the line i contains the string Si with uniquely upper-case letters. The total length of all n strings is not exceeded to 105.

Output

Print uniquely one integer which is the length of the longest common substring.

Examples

Input

ABCXYZ

XYZABC

XYABCZ

Output

3


Comments


  • 3
    I_love_NguyenLinh  commented on Dec. 8, 2018, 10:17 a.m.

    bài này cheat smallest < 20 mới AC :| khoai nhỉ