#ABC141E. Who Says a Pun?

Who Says a Pun?

题目描述

Given is a string SS of length NN.

Find the maximum length of a non-empty string that occurs twice or more in SS as contiguous substrings without overlapping.

More formally, find the maximum positive integer lenlen such that there exist integers l1l_1 and l2l_2 ( 1l1,l2Nlen+11 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

  • l1+lenl2l_1 + len \leq l_2

  • S[l1+i]=S[l2+i](i=0,1,...,len1)S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer lenlen, print 00.

给出长度为 NN 的字符串 SS

求在 SS 中连续出现两次或两次以上且不重叠的非空字符串的最大长度。

更正式地说,求存在满足以下条件的整数 l1l_1l2l_2 ( 1l1,l2Nlen+11 \leq l_1, l_2 \leq N - len + 1 ) 的最大正整数 lenlen

  • l1+lenl2l_1 + len \leq l_2
  • S[l1+i]=S[l2+i](i=0,1,...,len1)S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

如果没有 lenlen 这样的整数,则打印 00

输入格式

输入内容按以下格式标准输入:

NN
SS

输出格式

打印在 SS 中出现两次或两次以上的非空字符串的最大长度,该字符串为连续子串,不重叠。如果没有这样的非空字符串,则打印 00

样例 #1

样例输入 #1

5
ababa

样例输出 #1

2

样例 #2

样例输入 #2

2
xy

样例输出 #2

0

样例 #3

样例输入 #3

13
strangeorange

样例输出 #3

5

说明

数据规模与约定

  • 2N5×1032 \leq N \leq 5 \times 10^3
  • S=N|S| = N
  • SS 由小写英文字母组成。

样例 11 解释

满足条件的字符串是a"、"b"、"ab "和 "ba"。其中最大长度为 22 ,这就是答案。请注意,ab作为连续的子串在 SS 中出现了两次,但语句中并没有提到一对整数 l1l_1l2l_2 ,因此 l1+lenl2l_1 + len \leq l_2 .

样例 22 解释

没有满足条件的非空字符串。