← 返回题目列表

Codeforces · 30/E

E. 狡猾而聪明的密码

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

我们故事中的英雄科帕国王在他很小的时候就认为他的私人数据隐藏得不够安全,这对国王来说是不可接受的。这就是为什么他发明了棘手而聪明的密码(后来他了解到他的密码是奇数长度的回文),并使用它对他的所有数据进行编码。

Copa 害怕忘记密码,所以他决定将其写在一张纸上。他意识到以这种方式保存密码是不安全的,因此他决定按以下方式对其进行加密:从密码的开头和结尾处删除 x 个字符(x 可以是 0,并且 2x 严格小于密码长度)。他获得了密码的3部分。我们将其分别称为前缀、中间和后缀,前缀和后缀的长度相等,中间的长度总是奇数。他用这些部分制作了一个字符串 A + 前缀 + B + 中间 + C + 后缀,其中 A、B 和 C 是 Copa 发明的一些(可能是空的)字符串,“+”表示串联。

许多年过去了,就在昨天,国王科帕发现了写有他的密码的纸条。密码以及字符串A、B和C都被Copa完全忘记了,所以他要求你找到一个最大可能长度的密码,这个密码可以由Copa发明、加密和编写。

输入

输入包含单个小拉丁字母字符串,长度为 1 到 105 个字符。

输出

第一行应包含整数 k — 答案中密码非空部分的数量 ($$k \in \{1, 3\}$$)。在接下来的 k 行中,每一行输出两个整数 xi 和 li — 密码相应部分的开始和长度。按 xi 递增的顺序输出对。用一个空格将成对的数字分隔开。

起始位置 xi 应该是从 1 到输入字符串长度的整数。所有 li 必须为正数,因为您应该只输出非空部分。中间部分的长度必须是奇数。

如果有多个解,则输出任意一个。请注意,您的目标是最大化 li 的总和,而不是最大化 k。

示例

输入 #1

abacaba

输出 #1

1
1 7

输入 #2

axbya

输出 #2

3
1 1
2 1
5 1

输入 #3

xabyczba

输出 #3

3
2 2
4 1
7 2