On Oct 22, 10:17*am, Luciano Paulino da Silva
wrote:
Dear all,
Some time ago (http://groups.google.com.br/group/
microsoft.public.excel.worksheet.functions/browse_thread/thread/
6b068321053a5c90/c6dcff10540e4bc2?q=palindromes+excel+bernie&lnk=ol &)
Bernie Deitrick helped me to solve a problem related to palindromes
and repeats detection on a string of letters. At present, I need
perform some change on that macros in order to detect non-redundant
palindromes and repeats. In this way, for the sequence bellow my
solution it would be:

QGAGAAAAAAAAGGAGQGG

13 Palindromes detected
GAG
AGA
GAAAAAAAAG
AA
AAA
AAAA
AAAAA
AAAAAA
AAAAAAA
AAAAAAAA
AGGA
GG
GQG * * 1 * * * 3

Now the solution it would be:

QGAGAAAAAAAAGGAGQGG

13 Non-redundant Palindromes detected

GAG
GAAAAAAAAG
GG

The big palindromes should be preferred in the occurrences.
Thanks in advance,
Luciano

I'm not quite sure what you mean by "Non-redundant". I take it to mean
something like "maximal non-overlapping"

I didn't modify Bernie Deitrick's code (so it might have a different
input/output) but came up with the following:

'''''''''''''''''''''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''''''''''''''''''''''''

Function Reverse(S As String) As String
Dim i As Long, n As Long
n = Len(S)
For i = 1 To n
Reverse = Reverse & Mid(S, n - i + 1, 1)
Next i
End Function

Function FindMaxInitPalin(SearchString As String) As String
'Given a string it returns the longest initial segment which is a
palindrome
Dim i As Long, j As Long
Dim init As String
For i = 1 To Len(SearchString)
init = Mid(SearchString, 1, i)
If init = Reverse(init) Then j = i
Next i
FindMaxInitPalin = Mid(SearchString, 1, j)
End Function

Function FindMaxPalins(SearchString As String) As Variant
'returns a variant array consisting of maximal nonoverlapping
palindromes
Dim Palindromes As Variant
Dim InputString As String
Dim chomp As String
Dim n As Long

InputString = SearchString
Do While Len(InputString) 0
chomp = FindMaxInitPalin(InputString)
InputString = Mid(InputString, Len(chomp) + 1)
If Len(chomp) 1 Then
If IsEmpty(Palindromes) Then
ReDim Palindromes(1 To 1)
Palindromes(1) = chomp
Else
n = UBound(Palindromes)
ReDim Preserve Palindromes(1 To n + 1)
Palindromes(n + 1) = chomp
End If
End If
Loop
FindMaxPalins = Palindromes
End Function

Sub Main()
Dim SearchString As String
Dim Results As Variant
Dim i As Long

SearchString = InputBox("Enter a string")
Results = FindMaxPalins(SearchString)
If IsEmpty(Results) Then
Range("A1").Value = "No palindromes found"
Else
Range("A1").Value = UBound(Results) & " maximal palidromes
found: "
For i = 1 To UBound(Results)
Range("A1").Offset(i).Value = Results(i)
Next i
End If
End Sub


'''''''''''''''''''''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''

The function FindMaxPalins is the heart of the code. Main() is a
simple driver program that dumps the results in column A and can of
course be modified to put the output somewhere else. On your sample
input I get:

4 maximal palidromes found:
GAG
AAAAAAAA
GG
GQG

I notice that you didn't include GQG in your desired output. Was that
an oversight on your part? If not, I really don't know what you mean
by "nonredundant."

Hope that helps

-John Coleman