advi的字符串比较时间复杂性

Question

我正在研究一个问题，寻找给定字符串的完全重复的最短子串，如果不匹配，则返回字符串的长度。在

我的主要想法是从Juliana的回答中得到的（Check if string is repetition of an unknown substring），我用python2.7重写了算法。在

我认为它应该是O(n^2)，但我并不确定我是正确的，这是我的想法——因为在外循环中，它尝试用begin character进行迭代的可能性——它是O(n)外部循环，在内循环中，它逐个比较字符——这是O(n)内部比较。所以，总的时间复杂度是O(n^2)？如果我不正确，请帮助改正。如果我是正确的，请帮助确认。：）

输入和输出示例

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

我的代码

^{pr2}$

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]和{}。）