Reberland Linguistics

题意翻译

已知有长度为$n$的由小写字母构成的一个字符串。 现在对字符串进行一些操作 - 选择一个长度$\color{red}\text{大于}$ $4$的“根”字符串 - 然后在“根”字符串之后连接上任意个长度为2或3的“后缀”字符串。 - 唯一的限制条件是，不可以连续接上两个相同的“后缀”字符串。 现在求构造过程中，有可能被用作“后缀”的字符串共有多少种。$P.S:$多个同样的“后缀”字符串只算一种。 ### 输入 一行，一个长度为$n$的仅包含小写字母的字符串 ### 输出 第一行一个整数$k$，表示有$k$种可能的“后缀”。 接下来$k$行，按照字典序依次输出所有可能的“后缀”。 $5\le n\le10^4$

题目描述

First-rate specialists graduate from Berland State Institute of Peace and Friendship. You are one of the most talented students in this university. The education is not easy because you need to have fundamental knowledge in different areas, which sometimes are not related to each other. For example, you should know linguistics very well. You learn a structure of Reberland language as foreign language. In this language words are constructed according to the following rules. First you need to choose the "root" of the word — some string which has more than $ 4 $ letters. Then several strings with the length $ 2 $ or $ 3 $ symbols are appended to this word. The only restriction — it is not allowed to append the same string twice in a row. All these strings are considered to be suffixes of the word (this time we use word "suffix" to describe a morpheme but not the few last characters of the string as you may used to). Here is one exercise that you have found in your task list. You are given the word $ s $ . Find all distinct strings with the length $ 2 $ or $ 3 $ , which can be suffixes of this word according to the word constructing rules in Reberland language. Two strings are considered distinct if they have different length or there is a position in which corresponding characters do not match. Let's look at the example: the word $ abacabaca $ is given. This word can be obtained in the following ways: , where the root of the word is overlined, and suffixes are marked by "corners". Thus, the set of possible suffixes for this word is $ {aca,ba,ca} $ .

输入输出格式

输入格式

The only line contains a string $ s $ ( $ 5<=|s|<=10^{4} $ ) consisting of lowercase English letters.

输出格式

On the first line print integer $ k $ — a number of distinct possible suffixes. On the next $ k $ lines print suffixes. Print suffixes in lexicographical (alphabetical) order.

输入输出样例

输入样例 #1

abacabaca

输出样例 #1

3
aca
ba
ca

输入样例 #2

abaca

输出样例 #2

0

说明

The first test was analysed in the problem statement. In the second example the length of the string equals $ 5 $ . The length of the root equals 5, so no string can be used as a suffix.