строка сравнение сложность времени для консультации

Question

Я работаю над проблемой, чтобы найти полностью повторяющуюся кратчайшую подстроку заданной строки, а если нет совпадения, верните длину строки.

Моя основная идея узнана из ответа Юлианы здесь (Check if string is repetition of an unknown substring), я переписываю алгоритм в Python 2.7.

Я думаю, что это должно быть O(n^2), но не уверен, что я прав, вот моя мысль - так как во внешнем цикле он пытается запустить символ начала итерации с помощью - это O(n) внешний цикл, а в внутренний цикл, он сравнивает характер один за другим - это O(n) внутреннее сравнение. Итак, общая временная сложность - O(n^2)? Если я не прав, пожалуйста, помогите исправить. Если я прав, пожалуйста, помогите подтвердить. :)

Входной и выходной пример

catcatcat => 3 
aaaaaa=>1 
aaaaaba = > 7 

Мой код,

def rorate_solution(word): 
    for i in range(1, len(word)//2 + 1): 
     j = i 
     k = 0 
     while k < len(word): 
      if word[j] != word[k]: 
       break 
      j+=1 
      if j == len(word): 
       j = 0 
      k+=1 
     else: 
      return i 

    return len(word) 

if __name__ == "__main__": 
    print rorate_solution('catcatcat') 
    print rorate_solution('catcatcatdog') 
    print rorate_solution('abaaba') 
    print rorate_solution('aaaaab') 
    print rorate_solution('aaaaaa') 

Answer 1

Ваша оценка выполнения вашей повторной записи правильно.

---

Но Use just the preprocessing of KMP to find the shortest period of a string.

---

(Повторная запись может быть более простым:

def shortestPeriod(word): 
    """the length of the shortest prefix p of word 
    such that word is a repetition p 
    """ 
# try prefixes of increasing length 
    for i in xrange(1, len(word)//2 + 1): 
     j = i 
     while word[j] == word[j-i]: 
      j += 1 
      if len(word) <= j: 
       return i 

    return len(word) 

if __name__ == "__main__": 
    for word in ('catcatcat', 'catcatcatdog', 
       'abaaba', 'ababbbababbbababbbababbb', 
       'aaaaab', 'aaaaaa'): 
     print shortestBase(word) 

- ваш сравнивает word[0:i] с word[i:2*i] два раза подряд.)