View GitHub Repository pyalgs

Schedule Inspection
Subscribe
Passed
Push — master ( f0fa5b...9f7531 )
by Xianshun
01:21
created

LongestRepeatedSubstringSearch.lrs()   A

↳ Parent: LongestRepeatedSubstringSearch

Complexity

Conditions 4

Size

Total Lines 18

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 4
c 1
b 0
f 0
dl 0
loc 18
rs 9.2
1 

            


            
                                                                                                            
                                                                
            
                                    
            
            

                
                    2
                

                                    
                                                    
                
                
                
class LongestRepeatedSubstringSearch(object):

            


            
                                                                        
                            
            
                                    
            
            

                
                    3
                

                                    
                                                    
                
                
                
    @staticmethod

            


            
                                                                        
                            
            
                                    
            
            

                
                    4
                

                                    
                                                    
                
                
                
    def lrs(text, pattern):

            


            
                                                                        
                            
            
                                    
            
            

                
                    5
                

                                    
                                                    
                
                
                
        n = len(text)

            


            
                                                                        
                            
            
                                    
            
            

                
                    6
                

                                    
                                                    
                
                
                
        a = [''] * n

            


            
                                                                        
                            
            
                                    
            
            

                
                    7
                

                                    
                                                    
                
                
                
        for i in range(0, n):

            


            
                                                                        
                            
            
                                    
            
            

                
                    8
                

                                    
                                                    
                
                
                
            a[i] = text[i:]

            


            
                                                                        
                            
            
                                    
            
            

                
                    9
                

                                    
                                                    
                
                
                

            


            
                                                                        
                            
            
                                    
            
            

                
                    10
                

                                    
                                                    
                
                
                
        sorted(a)

            


            
                                                                        
                            
            
                                    
            
            

                
                    11
                

                                    
                                                    
                
                
                

            


            
                                                                        
                            
            
                                    
            
            

                
                    12
                

                                    
                                                    
                
                
                
        max_len = 0

            


            
                                                                        
                            
            
                                    
            
            

                
                    13
                

                                    
                                                    
                
                
                
        j = -1

            


            
                                                                        
                            
            
                                    
            
            

                
                    14
                

                                    
                                                    
                
                
                
        for i in range(0, n):

            


            
                                                                        
                            
            
                                    
            
            

                
                    15
                

                                    
                                                    
                
                
                
            l = LongestRepeatedSubstringSearch.lcp(a[i], pattern)

            


            
                                                                        
                            
            
                                    
            
            

                
                    16
                

                                    
                                                    
                
                
                
            if l > max_len:

            


            
                                                                        
                            
            
                                    
            
            

                
                    17
                

                                    
                                                    
                
                
                
                j = i

            


            
                                                                        
                            
            
                                    
            
            

                
                    18
                

                                    
                                                    
                
                
                
                max_len = l

            


            
                                                                        
                            
            
                                    
            
            

                
                    19
                

                                    
                                                    
                
                
                

            


            
                                                                        
                            
            
                                    
            
            

                
                    20
                

                                    
                                                    
                
                
                
        return (j, max_len)

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    21
                

                                    
                                                    
                
                
                

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    22
                

                                    
                                                    
                
                
                
    @staticmethod

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    23
                

                                    
                                                    
                
                
                
    def lcp(text, pattern):

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    24
                

                                    
                                                    
                
                
                
        i = 0

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    25
                

                                    
                                                    
                
                
                
        for i in range(min(len(text), len(pattern))):

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    26
                

                                    
                                                    
                
                
                
            if text[i] != pattern[i]:

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    27
                

                                    
                                                    
                
                
                
                return i

            


            
                                                                                                            
                                                                
            
                                    
            
            

                
                    28
                

                                    
                                                    
                
                
                
        return i

            


            
                                                        
            
                                    
            
            

                
                    29