#P1366. [Baltic2004]repeats

    ID: 378 传统题 1000ms 512MiB 尝试: 101 已通过: 25 难度: 8 上传者: 标签>CF2400提高+/省选-字符串周期倍数枚举后缀数组倍增计数排序Kasai 算法LCP+RMQST 表

[Baltic2004]repeats

[BOI2004] REPEATS

题目描述

如果字符串 ss 满足:

  • 对于一个数对 (k,l) (k≥1,l≥1)(k,l)~(k\ge 1,l\ge 1)。
  • ss 是由 kk 个长度为 ll 的字符串 tt 拼接成的。

那么 ss 就被称作是一个 (k,l) - repeat(k,l)\text{ - repeat} 串。

如 s=abaabaabaabas=\tt abaabaabaaba 就是一个 t=abat=\tt aba 的 (4,3) - repeat(4,3)\text{ - repeat} 串。

对于一个字符串 uu(仅含字符 a\texttt a 和 b\texttt b),你需要找出其中的一段是 (k,l) - repeat(k,l)\text{ - repeat} 串的连续的字符串,使 kk 尽可能大。

例如 u=babbabaabaabaaba‾bu=\tt babb\underline{abaabaabaaba}b,其中划线部分就是一个 (4,3) - repeat(4,3)\text{ - repeat} 串,这时 kk 的值最大。

输入格式

第一行一个整数 nn,代表 uu 的长度。

接下来 nn 行,每行一个字符(a\texttt a 或 b\texttt b),表示这个字符串。

输出格式

第一行一个数 kk。

第二行一个数 ll。

第三行一个数 pp,表示这个 (k,l) - repeat(k,l)\text{ - repeat} 串的开始位置(位置从 11 开始)。

如果有多种情况,输出任意一种。

样例 #1

样例输入 #1

17
b
a
b
b
a
b
a
a
b
a
a
b
a
a
b
a
b

样例输出 #1

4
3
5

提示

数据规模与约定

对于 100%100\% 的数据,有 1≤n≤5×1041\le n\le 5\times 10^{4},ui∈{a,b}u_i\in\{\tt a,b\}。

说明

译自 BalticOI 2004 Day2 A REPEATS