#T. Who Says a Pun?

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l

Type: RemoteJudge

2000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

给你一个字符串，请找到两个互相不重叠且完全相同的子串，并输出它的最大长度。

题目描述

長さ $N$ の文字列 $S$ が与えられます。

非空文字列であって、 $S$ の連続する部分文字列として重ならずに $2$ 回以上現れるもののうち、最長のものの長さを答えてください。

より厳密には、

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

を満たす整数 $l_1$ , $l_2$ ( $1\ \leq\ l_1,\ l_2\ \leq\ N\ -\ len\ +\ 1$ ) が存在するような正整数 $len$ の最大値を求めてください。そのような $len$ が存在しないときは、 $0$ を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$

输出格式

非空文字列であって、 $S$ の連続する部分文字列として重ならずに $2$ 回以上現れるもののうち、最長のものの長さを出力せよ。そのような非空文字列が存在しないときは、 $0$ を出力せよ。

样例 #1

样例输入 #1

5
ababa

样例输出 #1

样例 #2

样例输入 #2

2
xy

样例输出 #2

样例 #3

样例输入 #3

13
strangeorange

样例输出 #3

提示

制約

$2\ <\ =\ N\ <\ =\ 5\ \times\ 10^3$
$|S|\ =\ N$
$S$ は英小文字から成る

Sample Explanation 1

条件を満たす文字列として、a, b, ab, ba が考えられます。これらの長さの最大値 $2$ が答えです。 aba は $S$ の連続する部分文字列として $2$ 度現れますが、 $l_1\ +\ len\ \leq\ l_2$ を満たすような $l_1$ , $l_2$ が取れないことに注意してください。

Sample Explanation 2

条件を満たす非空文字列は存在しません。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended

Status: Done
Rule: IOI
Problem: 44
Start at: 2024-1-7 16:00
End at: 2024-2-18 8:00
Duration: 1000 hour(s)
Host: yuyongchao
Partic.: 15

#T. Who Says a Pun?

Who Says a Pun?

题面翻译

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

制約

Sample Explanation 1

Sample Explanation 2

北辰OI提高组第2周序列问题课后练习题👍

Status

Development

Support

#T. Who Says a Pun?

Who Says a Pun?

题面翻译

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

制約

Sample Explanation 1

Sample Explanation 2

北辰OI提高组第2周序列问题课后练习题👍

Status

Development

Support

Don't have an account?

SIGN IN