python在字符串中查找重复的子字符串

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)