在单词中找到最短的重复周期? [英] Finding shortest repeating cycle in word?

问题描述

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

I'm about to write a function which, would return me a shortest period of group of letters which would eventually create the given word.

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

For example word abkebabkebabkeb is created by repeated abkeb word. I would like to know, how efficiently analyze input word, to get the shortest period of characters creating input word.

推荐答案

O(n)解决方案.假定必须覆盖整个字符串.关键的观察结果是我们生成了模式并对其进行了测试，但是如果我们发现不匹配的内容，则必须包含我们已经测试过的整个字符串，因此我们不必重新观察那些字符. /p>

O(n) solution. Assumes that the entire string must be covered. The key observation is that we generate the pattern and test it, but if we find something along the way that doesn't match, we must include the entire string that we already tested, so we don't have to reobserve those characters.

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;

这篇关于在单词中找到最短的重复周期?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！