算法---重复的子字符串

题目

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:

输入: s = “aba”
输出: false
示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示：

1 <= s.length <= 104
s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/repeated-substring-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方法

方法一：

    fun repeatedSubstringPattern(s: String): Boolean {
        val length = s.length
        for (i in 1 until length) {
            if (length % i == 0 && s.substring(0, i).repeat(length / i) == s) {
                return true
            }
        }
        return false
    }

遍历的时候 直接对当前的字符进行n倍 进行equals 比较
注意：kotlin equals 可以用 == 替代 如果相比较内存地址 使用 ===

方法二：

    fun repeatedSubstringPattern2(s: String): Boolean {
        return "$s$s".indexOf(s, 1) < s.length
    }

如果存在重复字符串 拼接成2个字符串 一定可以在原字符串的长度前匹配到原字符串

总结

1.KMP算法很秀 别看这是一个简单题 但是做的好也很难