# 重复的子字符串
---

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

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

:::success

/*
	满足题解规则的已经至少是两倍的子字符串
	先两倍完整字符串，这时已经至少是4倍的字符串
	去掉合并字符串的首尾字符，至少还存在两倍的子符串的即满足规则
*/

func repeatedSubstringPattern(s string) bool {
	str := s + s
	str1 := str[1 : len(str) - 1]
	return strings.Contains(str1, s)
}


// 采用寻找乘积因子的方式

/*
该长度的子串是否可以多次构成原字符串,变种编程可以寻找最长子字符串
9 -> [1, 3], 10 ->[1,2,5], 12 [1, 2, 3, 6]
*/

func repeatedSubstringPattern(s string) bool {
	if len(s) == 1 {
		return false
	}
	length := len(s)
	return findSubStr([]byte(s), length / 2, length)
}

func findSubStr(b []byte, n, length int) bool {
	for i := 1; i <= n; i++ {
		if length % i == 0 { // 寻找乘积因子 9 -> [1, 3], 10 ->[1,2,5], 12 [1, 2, 3, 6] 主要是该长度的子串是否可以多次构成原字符串
			subStr := b[0 : i] // 寻找符合条件的子字符串， i为步长
			flag := true
			for j := i; j + i <= length; j += i {
				// 比较每一个步长为i的子串
				if !(string(subStr) == string(b[j : j + i])) { // 发现一个子串不一致就终止比较，长度为i的子串无法多次构成原字符串
					flag = false
					break
				}
			}
			if flag {
				return true
			}
		}
	}
	return false
}

// KMP算法

func repeatedSubstringPattern(s string) bool {
    return kmp(s)
}

func kmp(pattern string) bool {
    n := len(pattern)
    fail := make([]int, n)
    for i := 0; i < n; i++ {
        fail[i] = -1
    }
    for i := 1; i < n; i++ {
        j := fail[i - 1]
        for (j != -1 && pattern[j + 1] != pattern[i]) {
            j = fail[j]
        }
        if pattern[j + 1] == pattern[i] {
            fail[i] = j + 1
        }
    }
    return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0
}

:::

###### tags: `LeeCode`