找到最大的重複子字符串

Question

這是我寫的一個函數，需要一個非常長的文本文件。如包含整個教科書的文本文件。它會查找任何重複的子字符串並輸出最大的字符串。現在它不起作用，它只輸出我放入的字符串

例如，如果有一個整個句子被重複的拼寫錯誤。它會輸出這個句子;因爲它是整個文件中最大的。如果在輸入整個段落兩次時出現錯字，則會輸出該段落。

該算法採用第一個字符，找到任何匹配項，如果匹配，並且長度最大，則存儲子字符串。然後它需要前2個字符並重復。然後是前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會總是如此。相反，您需要查找子字符串是否在整個字符串中多次出現，然後更新計數。

這裏是例如蠻力算法，解決它： -

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")