在字符串中查找重复的子字符串[关闭]

Question

我正在Python中寻找一个函数，您可以在其中给出一个字符串作为输入，其中某个单词已重复多次，直到达到一定的长度。

输出就是那个单词。重复的单词不一定全部重复，也有可能根本没有重复。

例如：

"pythonpythonp" => "python"

"hellohello" => "hello"

"appleapl" => "apple"

"spoon" => "spoon"

有人可以给我一些关于如何编写这种函数的提示吗？

Answer 1

您可以通过重复子字符串一定次数并测试它是否等于原始字符串来实现。

你必须尝试每一个可能的字符串长度，除非你将其保存为变量

代码如下：

def repeats(string):
    for x in range(1, len(string)):
        substring = string[:x]

        if substring * (len(string)//len(substring))+(substring[:len(string)%len(substring)]) == string:
            print(substring)
            return "break"

    print(string)

repeats("pythonpytho")

Answer 2

首先构建前缀数组。

反向循环它，并在第一次发现字符串中重复的内容时停止（即，它有一个

str.count()>1

。

现在，如果相同的子字符串紧邻其自身，您可以将其作为您要查找的单词返回，但是您必须考虑

'appleappl'

示例，其中建议的算法将返回

appl

。为此，当您发现字符串中多次存在的子字符串时，您将返回该子字符串加上其下一次出现之间的任何内容，即对于

'appleappl'

您返回

'appl' +'e' = 'apple'

。如果没有找到这样的字符串，您将返回整个单词，因为没有重复。

def repeat(s):
    prefix_array=[]
    for i in range(len(s)):
        prefix_array.append(s[:i])
    #see what it holds to give you a better picture
    print prefix_array

    #stop at 1st element to avoid checking for the ' ' char
    for i in prefix_array[:1:-1]:
        if s.count(i) > 1 :
            #find where the next repetition starts
            offset = s[len(i):].find(i)

            return s[:len(i)+offset]
            break

    return s


print repeat(s)