重复的子字符串

原题链接：459.重复的子字符串

题目描述

给定一个非空的字符串，判断它是否可以由它的某个连续的子串(不包括自己)重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例1：

输入："abcabc"
输出：True
解释：可由子字符串"ab"重复两次构成。

示例2：

输入："aabb"
输出：False
解释：无法找到一个连续的子串，使其重复多次构成"aabb"。

解释

方法一：
可以发现，字符串具有这样的一个性质“将一个字符串s复制后相连形成ss，并移除第一个和最后一个字符得到字符串xy，s是xy的子串当且仅当s可由它的某个连续的子串(不包括自己)重复多次构成”。

证明：
$\Rightarrow$
$\Leftarrow$
因为$s$可由它的某个连续的子串(不包括自己)重复多次构成，不妨假设$s$由$s’$重复$n$次构成。那么字符串$ss$由$2n$个$s’$构成，故当移除第一个和最后一个字符所得到的字符串$xy$，还有$2n-2$个完整且相连的$s’$。由于$s’ \neq s$且$n$为正整数，所以$n\geq 2$，易得$2n-2\geq n$。故$s$是$xy$的子串。

$\underset{\uparrow}{a}$