python - 建议的字符串比较时间复杂度

Question

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

我的主要想法是从 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')

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] 连续两次。)