寻找单词中最短的重复周期？

Question

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

例如单词abkebabkebabkeb由重复的abkeb单词创建。我想知道如何有效地分析输入单词，以使字符创建输入单词的时间最短。

Answer 1

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;

Answer 2

在bcbdbcbcbdbc等情况下适用。

Answer 3

我想出了一个简单的解决方案，即使使用非常大的字符串也可以完美地工作。PHP实现：

Answer 4

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

Answer 5

这是PHP的示例：

Answer 6

我相信有一个非常优雅的递归解决方案。许多建议的解决方案解决了字符串以模式的一部分结尾（例如abcabca）时的额外复杂性。但我认为这不是必需的。

Answer 7

我根据您的帖子找到了一个解决方案，可能采用不完整的模式：

Answer 8

我的解决方案：这个想法是从零位置找到一个子串，以使其等于相同长度的相邻子串，当找到这样的子串时，返回该子串。请注意，如果找不到重复的子字符串，我将打印整个输入字符串。

Answer 9

正则表达式解决方案：

Answer 10

这是我使用队列提出的解决方案，它通过了代码部队中类似问题的所有测试用例。问题编号是745A。

Answer 11

超级延迟的答案，但是我在采访中提出了问题，这是我的答案（可能不是最佳答案，但它也适用于奇怪的测试用例）。