Algorithm Implementation/Strings/Longest repeated substring
A search conducted within one string for its longest repeated substring. This function finds the non-overlapping repeats as opposed to the overlapping repeats of other implementations. That is to say, for banana, this form will find only an and not the overlapping ana. The function has application in the pattern search of cipher text. A detected pattern of this non-overlapping kind can be used to find a Caesar cipher's key length when certain other factors obtain.
VBA[edit | edit source]
Returns the longest repeated non-overlapping substring for a single string, and the number of repeats. In contests, if length is matched, the substring with most repeats is returned. If still matched, the one that was found first is returned. The worst case is for no repeats found where the number of cycles becomes maximum at (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 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