CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    May 2012
    Posts
    2

    Finding the 3 longest palindromes

    Hello guys,
    as a novice C# programmer (I come from MatLab and Java) I'm being asked to create an algorithm that finds, given a string, the three longest palindromes contained in it, and returns them, with their starting index and length. For example, the output for string, “sqrrqabccbatudefggfedvwhijkllkjihxymnnmzpop” should be:

    Text: hijkllkjih, Index: 23, Length: 10
    Text: defggfed, Index: 13, Length: 8
    Text: abccba, Index: 5 Length: 6


    I'm downloading #develop now, and I'll give it a go, but does anybody have any ideas/solutions? Thanks

  2. #2
    Join Date
    Feb 2012
    Location
    Strasbourg, France
    Posts
    116

    Re: Finding the 3 longest palindromes

    Just writing my draft ideas on topic :

    Finding start of palindrom just going from left to right can be problematic in my mind as you would have to check **** tons of combinaisons.

    Though you can reduce by reading character after character your string and check for occurences of 2 times the same letter. Why ?

    Minimal palindrome size is "aa".

    So here's my idea in pseudo code
    Code:
    Function 1 (string input)
    {
    	for each character in input compare to the next
    	if the 2 characters are equal
    	then execute function 2
    	loop
    	return results
    }
    
    Function2 (int position_start)
    {
    	this function will check both left and right character for a given position (+1 for a give, depends if the pos start is the left or right character of initial couple) and move one character far from the start each loop
    	loop while they are equal
    	return length and index (as you'll have it)
    }
    After that c# is quite simillar to Java so you shouldn't have too many problems.

  3. #3
    Join Date
    May 2012
    Posts
    2

    Re: Finding the 3 longest palindromes

    Thanks Erendar. Your first thoughts matched mine. Though I did some more reading, and it turns out there is much more. Our basic assumption, that the minimal palindrome is "aa", is wrong, because that is only true if we consider a n empty space to be the only possible center. But actually, a letter may also be a center, so "a" is the minimal palindrome.
    After that, there is tons more to consider. It is easy to solve in O(3), more difficult in O(2). People have found a linear time solution (fantastic!), documented at http://www.akalin.cx/longest-palindrome-linear-time for your own curiosity.

    Thank you very much

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured