# 該解答很簡單,大家閲讀一遍就會明白
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle or not haystack:  # 任一為空字符,必然沒結果
            return -1
        else:
            n_start = needle[0]
            length = len(needle)
            min_index = 100000 # 題目裏規定≤10^4
            for i in range(len(haystack)):
                if haystack[i] == n_start and haystack[i:i+length] == needle:  #首一樣再判斷
                    min_index = min(i,min_index)
                else:
                    continue
            
            if min_index != 100000:
                return min_index
            else:
                return -1

# example 1
def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

# 基本操作(最內層）：total += x
# 執行次數（直接讓規模為n）：for x in arr每次循環執行一次加和操作, 總計會執行 n 次
# 時間複雜度：O(n)


# example 2
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):                     # 外層循環：控制比較的輪數
        for j in range(n - i - 1):         # 內層循環：每輪比較相鄰元素
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 嵌套循環，兩層 for
# 執行次數: 外層for,執行了 n 次（i 從 0 到 n-1); 內層循環， 第 1 次外循環（i = 0）：j 運行 0 ~ n-2，共執行 n-1 次，第 2 次外循環（i = 1）：j 運行 0 ~ n-3，共執行 n-2 次，第 3 次外循環（i = 2）：執行 n-3 次...
# 第 n-1 次外循環（i = n-1）：執行 0 次
# 所以，總共的比較次數是——規模為n，加和內層循環次數，即(n−1)+(n−2)+(n−3)+⋯+1+0
# 時間複雜度：O(n(n-1)/2) 等價於 O(n^2）

# example 1
def find_max(arr):
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

# 分析：只用了常數個變量：max_val、x。空間複雜度：O(1)


# example 2
def copy_array(arr):
    new_arr = arr[:]
    return new_arr
# 分析：“:” 表示不指定起始和結束位置，默認從頭到尾。即複製了一個大小為 n 的數組，空間複雜度：O(n)

# 原始字符串
s =  a b a b
# 拼接後
s + s = a b a b a b a b
# 去掉首尾元素
(s + s)[1:-1] = b a b a b a

s in "b a b a b a"--> True

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s_new = s + s
        s_new_part = s_new[1:-1]
        if s in s_new_part:
            return True
        else:
            return False

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # 暴力法
        n = len(s)
        for L in range(1, n // 2 + 1):
            if n % L == 0:
                if s[:L] * (n // L) == s:  # 子串*重複次數為字符串本身
                    return True
        return False