459. 重复的子字符串

题目描述

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

示例 1:

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

示例 2:

输入: s = “aba”
输出: false

示例 3:

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

解法一：枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func repeatedSubstringPattern(s string) bool {
    n := len(s)
    for i := 1; i * 2 <= n; i++ {
        if n % i == 0 {
            match := true
            for j := i; j < n; j++ {
                if s[j] != s[j - i] {
                    match = false
                    break
                }
            }
            if match {
                return true
            }
        }
    }
    return false
}

解法二：KMP 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func repeatedSubstringPattern(s string) bool {
    // 注意：当 s 只由一个字符组成时（如 s="a"），本函数应该返回 false
    a := s + s
    // next[i] 的值表示的是 s 的子串 s[0...i] 最长且相等的真前缀与真后缀的长度
    next := make([]int, len(s))
    for i, j := 0, 1; j < len(s); j++ {
        // i 表示前一个子串的最长且相等的真前缀与真后缀的长度。注意 i 从 0 开始
        // 因为只有一个字符的字符串没有真前缀与真后缀
        // j 指向当前子串的末尾字符
        for i > 0 && s[i] != s[j] {
            i = next[i]
        }
        if s[i] == s[j] {
            i++
        }
        next[j] = i
    }

    for i, j := 1, 0; i < len(a)-1; i++ {
        for j > 0 && s[j] != a[i] {
            j = next[j]
        }
        if s[j] == a[i] {
            j++
        }
        if j == len(s) {
            return true
        }
    }

    return false
}