;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil nil t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Z-algorithm
;;;

(declaim (inline make-z-array))
(defun make-z-array (vector &key (test #'eql))
  "Returns a vector Z of the same length as VECTOR. An element Z[i] is the
length of the longest substring starting from i which is also a prefix of
VECTOR."
  (declare (vector vector))
  (let* ((size (length vector))
         (pos 1)
         (width 0)
         (res (make-array size
                          :element-type '(integer 0 #.most-positive-fixnum)
                          :initial-element 0)))
    (declare ((integer 0 #.most-positive-fixnum) pos width))
    (unless (zerop size)
      (setf (aref res 0) size)
      (loop while (< pos size) 
            do (loop while (and (< (+ pos width) size)
                                (funcall test
                                         (aref vector width)
                                         (aref vector (+ pos width))))
                     do (incf width))
               (setf (aref res pos) width)
               (if (zerop width)
                   (incf pos)
                   (loop for offset of-type (integer 0 #.most-positive-fixnum) from 1
                         while (and (< (+ pos offset) size)
                                    (< (+ offset (aref res offset)) width))
                         do (setf (aref res (+ pos offset))
                                  (aref res offset))
                         finally (incf pos offset)
                                 (decf width offset)))))
    res))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline read-line-into))
(defun read-line-into (buffer-string &key (in *standard-input*) (term-char #\Space))
  "Receives ASCII inputs and returns multiple values: the string and the end
position.

This function calls READ-BYTE to read characters though it calls READ-CHAR
instead on SLIME because SLIME's IO is not bivalent."
  (declare (inline read-byte)
           #-swank (sb-kernel:ansi-stream in))
  (loop for c of-type base-char =
           #-swank (code-char (read-byte in nil #.(char-code #\Newline)))
           #+swank (read-char in nil #\Newline)
        for idx from 0
        until (char= c #\Newline)
        do (setf (char buffer-string idx) c)
        finally (when (< idx (length buffer-string))
                  (setf (char buffer-string idx) term-char))
                (return (values buffer-string idx))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (s (make-string n :element-type 'base-char))
         (res 0))
    (declare (uint62 res)
             (base-string s))
    (read-line-into s)
    (dotimes (start n)
      (let* ((s (subseq s start))
             (z-array (make-z-array s)))
        (declare (simple-base-string s))
        (loop for j from 1 below (length z-array)
              do (setq res (max res (min j (aref z-array j)))))))
    (println res)))

#-swank (main)


Measured memory_bytes: 88552