Ad:

C++ Discussion Thread
Unsolved
Views: 1325

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Dec 10th, 2008

Palindrome re-visited

Expand Post »

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

C++ Syntax (Toggle Plain Text)
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;
}
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/200...lindromes.html

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

shankhs

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

58 posts
since Jan 2008

Permalink

Dec 11th, 2008

Re: Palindrome re-visited

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.

shankhs

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

58 posts
since Jan 2008

Permalink

Dec 11th, 2008

Re: Palindrome re-visited

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

ithelp

Reputation Points: 769

Solved Threads: 128

Banned

Offline

1,910 posts
since May 2006

Permalink

Dec 11th, 2008

Re: Palindrome re-visited

Can i get another algorithm???

shankhs

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

58 posts
since Jan 2008

Permalink

Dec 11th, 2008

Re: Palindrome re-visited

From the link you posted:

Quote ...

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

Quote ...

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.

mrboolf

Reputation Points: 134

Solved Threads: 18

Junior Poster

Offline

182 posts
since Jun 2008

Permalink

Dec 11th, 2008

Re: Palindrome re-visited

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

c++ Syntax (Toggle Plain Text)
#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;   
}
#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;   
}

Last edited by cikara21; Dec 11th, 2008 at 9:20 am. Reason: strcmp to stricmp

cikara21

Reputation Points: 47

Solved Threads: 69

Posting Whiz

Offline

340 posts
since Jul 2008

Permalink

Dec 11th, 2008

Re: Palindrome re-visited

Or...

c++ Syntax (Toggle Plain Text)
 
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;   
}
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;   
}

cikara21

Reputation Points: 47

Solved Threads: 69

Posting Whiz

Offline

340 posts
since Jul 2008

Permalink

Dec 12th, 2008

Re: Palindrome re-visited

Click to Expand / Collapse Quote originally posted by mrboolf ...

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.

Last edited by shankhs; Dec 12th, 2008 at 1:04 am.

shankhs

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

58 posts
since Jan 2008

Permalink

Dec 12th, 2008

Re: Palindrome re-visited

Click to Expand / Collapse Quote originally posted by cikara21 ...

Or...
c++ Syntax (Toggle Plain Text)
 
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;   
}
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.

shankhs

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

58 posts
since Jan 2008

Permalink

Dec 12th, 2008

Re: Palindrome re-visited

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:

cpp Syntax (Toggle Plain Text)
// 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);
   }
// 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.

Last edited by dougy83; Dec 12th, 2008 at 8:12 am. Reason: line numbers

dougy83

Reputation Points: 85

Solved Threads: 45

Posting Whiz in Training

Offline

275 posts
since Jun 2007

Page 1
2
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: How to Find The user input ?

Next Thread in C++ Forum Timeline: Get File creation Date

DaniWeb Message

Cancel Changes

User Name
Password