Question

How to find the longest repeating substring in a string with Python

Answer 1

def longest_common_prefix(sub1, sub2):  
    n = min(len(sub1), len(sub2));  
       
    for i in range(0, n):  
        if (sub1[i] != sub2[i]):  
            return sub1[0:i];  
               
    return sub1[0:n];  
      
s = "pythonphpjavacdartcppjavacsharp";  
lrs = "";  
size = len(s);  
   
for i in range(0, size):  
  for j in range(i+1, size):  
    lcp = longest_common_prefix(s[i:size], s[j:size]);  
    if (len(lcp) > len(lrs)):  
        lrs = lcp;    
           
print(lrs);  
   
   
   
   
'''
run:
   
pjavac
   
'''

 

70+ SQL courses for beginners and professionals

Answer 2

def longest_common_prefix(sub1, sub2):  
    n = min(len(sub1), len(sub2));  
     
    for i in range(0, n):  
        if (sub1[i] != sub2[i]):  
            return sub1[0:i];  
             
    return sub1[0:n];  
    
def longest_repeating_substring(s):
    suffixes = []
    size = len(s)
    
    for i in range(size):
        suffixes.append(s[i:size])
 
    suffixes.sort()
 
    max_len = 0
    for sub1, sub2 in zip(suffixes, suffixes[1:]):
        lcp = longest_common_prefix(sub1, sub2)
        if len(lcp) > max_len:
            max_len = len(lcp)
            lrs = lcp
 
    return lrs
    
s = "pythonphpjavacdartcppjavacsharp";  
 
print(longest_repeating_substring(s));  
 
 
 
 
'''
run:
 
pjavac
 
'''
 

 

70+ SQL courses for beginners and professionals