在单词中找到最短的重复循环？

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]

Answer 2

O(n) 解。假设必须覆盖整个字符串。关键的观察是我们生成模式并测试它，但是如果我们发现一些不匹配的东西，我们必须包含我们已经测试过的整个字符串，这样我们就不必重新观察这些字符。

def pattern(inputv):
    pattern_end =0
    for j in range(pattern_end+1,len(inputv)):

        pattern_dex = j%(pattern_end+1)
        if(inputv[pattern_dex] != inputv[j]):

            pattern_end = j;
            continue

        if(j == len(inputv)-1):
            print pattern_end
            return inputv[0:pattern_end+1];
    return inputv;