python - 字符串比较时间复杂度，以获取建议

我正在研究一个问题来寻找给定字符串的完全重复的最短子串，如果没有匹配，则返回字符串的长度。
我的主要想法是从juliana的答案中学习到的（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')

最佳答案

您对重写运行时的评估是正确的。
但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)

-你的比较是连续两次