← 返回题目列表

AtCoder · abc141_e

E. 谁说双关语?

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给定的是一个字符串 S 长度 N.

求出出现两次或以上的非空字符串的最大长度 S 作为连续的子字符串,不重叠。

更正式地说,找到最大正整数 len 使得存在整数 l_1 和 l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 )满足以下条件:

  • l_1 + len \leq l_2

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

如果没有这样的整数 len,打印 0.

约束

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

输入

输入由标准输入按以下格式给出:

N
S

输出

打印出现两次或多次的非空字符串的最大长度 S 作为连续的子字符串,不重叠。如果不存在这样的非空字符串,则打印 0 代替。


示例输入 1

5
ababa

示例输出 1

2

满足条件的字符串为: a, b, ab,和 ba。其中最大长度为 2,这就是答案。 请注意 aba 出现两次 S 作为连续子字符串,但没有整数对 l_1 和 l_2 在声明中提到, l_1 + len \leq l_2.


示例输入 2

2
xy

示例输出 2

0

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


示例输入 3

13
strangeorange

示例输出 3

5