python - 寻找最大的重复子串

Question

这是我编写的一个函数，它需要一个很长的文本文件。例如包含整本教科书的文本文件。它将找到任何重复的子字符串并输出最大的字符串。但是现在它不起作用，它只是输出我输入的字符串

例如，如果出现重复整个句子的拼写错误。它会输出那句话；鉴于它是整个文件中最大的。如果有一个错字，整个段落被输入了两次，它会输出该段落。

该算法获取第一个字符，找到任何匹配项，如果匹配且长度最大，则存储子字符串。然后它取前 2 个字符并重复。然后是前 3 个字符。等等。然后它将重新开始，除了从第 2 个字符而不是第 1 个字符开始。然后从第 3 个字符开始一直往回走。

def largest_substring(string):

  length = 0
  x,y=0,0

  for y in range(len(string)):        #start at string[0, ]
    for x in range(len(string)):      #start at string[ ,0]
     substring = string[y:x]          #substring is [0,0] first, then [0,1], then [0.2]... then [1,1] then [1,2] then [1,3]... then [2,2] then [2,3]... etc.
     if substring in string:          #if substring found and length is longest so far, save the substring and proceed.
      if len(substring) > length:
       match = substring
       length = len(substring)

Answer 1

我认为您的逻辑在这里有缺陷，因为它总是返回整个字符串，因为它检查子字符串是否在整个字符串中，这始终为真，因此语句 if substring in string 将始终为 true .相反，您需要查找子字符串在整个字符串中是否多次出现，然后更新计数。

这是解决它的蛮力算法的例子:-

import re

def largest_substring(string):

    length = 0
    x=0
    y=0

    for y in range(len(string)):       
        for x in range(len(string)):     
            substring = string[y:x]                   
            if len(list(re.finditer(substring,string))) > 1  and len(substring) > length:
                match = substring
                length = len(substring)
    return match


print largest_substring("this is repeated is repeated is repeated")