Palindrome re-visited

[shankhs]

I am searching an efficient algorithm to find all the palindromes in a string(actually I have to find the largest palindrome in a string)..
Here is my code

string palindrome(string str)
{
	
	int n=sz(str);
	
	for(int l=n-1;l>=0;l--)//Palindrome can be of any size.
	{
		for(int i=0;i<n-l+1;i++)
		{
			int j=i+l-1;
			
			string str2=str.substr(i,j-i+1);
			
			if(check_pal(str2)) return str2;//check_pal simply checks whether //the string is palindrome or not.
		}
	}
	
	string t1="";
	return t1;
}

This is an O(n^3)(since check_pal requires another loop),I searched and got this:
http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html

But I cant understand a word of it What is his algo? How is it linear?
Please help me...

[shankhs]

Hey guys Please help me...
I am new to algorithms if there is an algorithm to find longest palindrome in a string just give me a link thats enough I will try my best to understand that.
Thankyou.

[ithelp]

Looks like that was his PHD thesis , you may not be able to understand it at all.

[shankhs]

Can i get another algorithm???

[mrboolf]

From the link you posted:

A naive algorithm for finding palindromes calculates all positions of an input array, and for each of those positions, calculates the length of the longest palindrome around that position.

That shouldn't be much difficult to implement, and

For each position, this function may take an amount of steps linear in the length of the array, so this is a quadratic-time algorithm.

Give it a try and then post your efforts in case you need help.

[cikara21]

This is a simple algorithm..You can learn from this..

#define MAX 128
bool check(const char *str, const char *ori)
{
   return ((stricmp(str,ori)==0)?true:false);
}

std::string palindrome(const char *str)
{
   int size=strlen(str);
   if(size>=MAX)
      return "failed";
   char reverse_str[MAX]={NULL};
   for(int i=0,j=((size)-1);i<size;i++,j--)
      reverse_str[i]=str[j];
   if(check(reverse_str,str))
      return reverse_str;
   return "it's not a palindrome";
}

int main()
{
   std::string m_str=palindrome("dlrow olleh hello world");
   std::cout<<m_str;
   std::cin.get();
   return 0;   
}

[cikara21]

Or...

bool check(const std::string str, const std::string ori)
{
   return ((stricmp(str.c_str(),ori.c_str())==0)?true:false);
}

std::string palindrome(const std::string str)
{
   int size=str.length();
   std::string reverse_str;
   for(int i=((size)-1);i>=0;i--)
      reverse_str.push_back(str[i]);
   if(check(reverse_str,str))
      return reverse_str;
   return "it's not a palindrome";
}

int main()
{
   std::string m_str=palindrome("dlrow olleh hello world");
   std::cout<<m_str.c_str();
   std::cin.get();
   return 0;   
}

[shankhs]

From the link you posted:

That shouldn't be much difficult to implement, and

Give it a try and then post your efforts in case you need help.

If you see the code in my first post I have done exactly that .the first loop determines the length of the substring to be checked and the second loop checks for each position in the array to get the substring of the specified length.
But this is giving me TLE..I need to optimize it.

[shankhs]

Or...

bool check(const std::string str, const std::string ori)
{
   return ((stricmp(str.c_str(),ori.c_str())==0)?true:false);
}

std::string palindrome(const std::string str)
{
   int size=str.length();
   std::string reverse_str;
   for(int i=((size)-1);i>=0;i--)
      reverse_str.push_back(str[i]);
   if(check(reverse_str,str))
      return reverse_str;
   return "it's not a palindrome";
}

int main()
{
   std::string m_str=palindrome("dlrow olleh hello world");
   std::cout<<m_str.c_str();
   std::cin.get();
   return 0;   
}

My problem is to find longest substring that is a palindrome not to check whether the string is palindrome or not.

[dougy83]

I have an dumb idea, what about an operation like convolving the test string with itself; i.e. doing a sliding comparision of the elements of the test string with the reversed-test-string. The longest consecutive string of matching elements is the longest palindrome.

Here's the code:

// do some convolution
string getLongestPalindrome(string fwd){
   string rev = string(fwd.rbegin(), fwd.rend());
   int sz = fwd.size();
   int maxcount = 0, maxstart = 0;
   int start = 0, end = 0, count = 0;

   for(int overlap = 1; overlap <= 2*sz; overlap++){
      count = 0;
   	for(int i = 0; i < overlap; i++){
   	   int index1 = sz - overlap + i;
   		if(index1 >= 0 && index1 < fwd.size() && i < rev.size() && fwd[index1] == rev[i]){
   		   if(!count){
               start = i;
               end = i;
               }

            count++;
            }
         else{
            if(count > maxcount){
               maxcount = count;
               maxstart = start;
               }

            count = 0;
            }
   		}
   	}

   if(count > maxcount){
      maxcount = count;
      maxstart = start;
      }

   return rev.substr(maxstart, maxcount);
   }

Less complexity than your above snippet. Note that you don't actually have make a copy of the reverse string; I just did that because it was clearer in my head - you can just change the index on line 11/12 and point it into the fwd string.

[cikara21]

K then..

bool check(const std::string str)
{
   int s=(int)str.length();
   std::string t;
   for(int i=s-1;i>=0;i--)
      t.push_back(str[i]);
   return ((stricmp(str.c_str(),t.c_str())==0)?true:false);
}

std::string palindrome(const std::string str)
{
   int s=(int)str.length();
   std::string lons;
   for(int i=0;i<s;i++)
      for(int j=s-1;j>i;j--)
      {
         std::string n=str.substr(i,j-i+1);
         if(check(n))
            if(n.length()>lons.length())
               lons=n;
      }
   return lons;
}

int main()
{
   std::string m_str=palindrome("bustdlrow ollehhellodush");
   std::cout<<m_str.c_str();
   std::cin.get();
   return 0;   
}