# 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
'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
```