演算法實現/字串/最長重複子串

在一個字串中搜索其最長的重複子串。此函式查詢的是非重疊重複，而不是其他實現中的重疊重複。也就是說，對於banana，此形式只會找到an，而不會找到重疊的ana。該函式在密文模式搜尋中應用。當某些其他因素滿足時，可以利用這種非重疊模式來找到凱撒密碼的金鑰長度。

VBA

返回單個字串的最長重複非重疊子串及其重複次數。在競賽中，如果長度相同，則返回重複次數最多的子串。如果仍然匹配，則返回先找到的子串。最壞情況是未找到重複，此時迴圈次數達到最大值(0.5*n)^2。

Function LongestRepeatSubstring(sIn As String, Optional nSS As Long) As String
    'finds longest repeated non-overlapping substring and number of repeats
    'LongestRepeatSubstring is output containing longest substring 
    'sIn is input parameter containing string to test
    'nSS is output parameter,if provided, contains number of found repeats
    
    Dim s1 As String, s2 As String, X As Long
    Dim sPrev As String, nPrev As Long, nLPrev As Long
    Dim nL As Long, nTrial As Long, nPos As Long, vAr as Variant
        
    nL = Len(sIn)
    For nTrial = Int(nL / 2) To 1 Step -1
        For nPos = 1 To (nL - (2 * nTrial) + 1)
            X = 0
            s1 = Mid(sIn, nPos, nTrial)
            s2 = Right(sIn, (nL - nPos - nTrial + 1))
            vAr = Split(s2, s1)            
            X = UBound(vAr) - LBound(vAr)
            If X > 0 Then
                If nPrev < X Then
                    sPrev = s1
                    nPrev = X
                End If
            End If
        Next nPos
        If nPrev <> 0 Then
            LongestRepeatSubstring = sPrev
            nSS = nPrev
            Exit Function
        End If
    Next nTrial
End Function