algorithm - 在word中找到最短的重复周期？

Question

我将要编写一个函数，它会返回一组最短的字母，这些字母最终会创建给定的单词。

例如单词 abkebabkebabkeb 是由重复的 abkeb 单词创建的。我想知道，如何有效地分析输入词，以获得创建输入词的字符的最短周期。

Answer 1

这是一个正确的 O(n) 算法。第一个 for 循环是 KMP 的建表部分。有各种证据表明它总是在线性时间内运行。

因为这个问题有 4 个以前的答案，没有一个是 O(n) 和正确的，我对这个解决方案的正确性和运行时间进行了大量测试。

def pattern(inputv):
    if not inputv:
        return inputv

    nxt = [0]*len(inputv)
    for i in range(1, len(nxt)):
        k = nxt[i - 1]
        while True:
            if inputv[i] == inputv[k]:
                nxt[i] = k + 1
                break
            elif k == 0:
                nxt[i] = 0
                break
            else:
                k = nxt[k - 1]

    smallPieceLen = len(inputv) - nxt[-1]
    if len(inputv) % smallPieceLen != 0:
        return inputv

    return inputv[0:smallPieceLen]