【Leetcode_總結】 459. 重複的子字元串 - python

Q：

給定一個非空的字元串，判斷它是否可以由它的一個子串重複多次構成。給定的字元串隻含有小寫英文字母，并且長度不超過10000。

示例 1:

輸入: "abab"

輸出: True

解釋: 可由子字元串 "ab" 重複兩次構成。
      

示例 2:

輸入: "aba"

輸出: False      

思路1：使用KMP算法，傳回的條件是 p 為next [-1] p > 0 and size % (size - p) 代碼如下：

class Solution:
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        size = len(s)
        next = [0] * size
        for i in range(1, size):
            k = next[i - 1]
            while s[i] != s[k] and k:
                k = next[k - 1]
            if s[i] == s[k]:
                next[i] = k + 1
        p = next[-1]
        return p > 0 and size % (size - p) == 0
           

思路2：

如果字元串重複的，那麼同一個字元串相加之後，内部必然會有重複，如abab 相加後為 abababab 字元串存在于[-1:1]區間内

如果是本身不是重複的字元串 如aba 那麼相加後為abaaba 在區間[-1:1]内不存在原子串，代碼如下：

class Solution:
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return s in (s*2)[1:-1]