Palindrome in text

[nirbilcahn]

http://ideone.com/H7YIwR

Here's my code to find palindrome in string..But surely it's too slow..Is there any good algorithms for such problems..And for some cases it's not giving the right answer.Thanks for the help.

[Trap910]

Your code has lot of constraint to check, but there is an simple solution for this one, just reverse the given string and compare it with the original string, if it matches then its palindrome or else it is not a palindrome...here is a code sample

int main()
{
int len,j,i;
char str[10],rev[10];
printf("Enter the string");
gets(str);
len=strlen(str);

j=len-1;
for(i=0;i<len;i++)
{
printf("%c",str[j]);
rev[i]=str[j];
j--;
}

if(strcmp(str,rev)==0)
printf("palindrom");
else
printf("Not palindrome");
return 0;
}

[nirbilcahn]

No,That's not what I meant... At least I'm not that dumb that to find if a string is palindrome or not I'll do this kind of checking :-D
My code finds every palindrome in input text and ignores punctuation and checks for alphabets ..
So,if I input -> i am a cat lover c attac games blah....blah..halb...

so,it'll output ->ama cattac atta tt blahhalb

Not just the string itself.

[vijayan121]

#include <string>
#include <cctype>
#include <algorithm>
#include <iostream>

bool is_palindrome( const std::string& str )
{
    std::string s ;
    for( char c : str ) if( std::isalpha(c) ) s += std::toupper(c) ;
    return !s.empty() && std::equal( s.begin(), s.begin() + s.size()/2, s.rbegin() ) ;
}

int main()
{
    const char* const phrases[]
    {
        "A man, a plan, a canal - Panama!", // yes
        "not palindrome", // no
        "No lemon, no melon", // yes
        "Not lemon, not melon", // almost, but no
        "Never odd or even" // yes
    };
    for( auto cstr : phrases ) if( is_palindrome(cstr) ) std::cout << cstr << '\n' ;
}

http://ideone.com/fhsyFy

[sepp2k]

OP doesn't have an array of strings where he wants to check each element string. He has one string of which he wants to check every substring. Iterating over all possible substrings and calling is_palindrome on each of them (which is basically what the OP is doing now - albeit in a needlessly complicated -- and apparently in some cases broken -- way) leads to a O(n^3) runtime. The question is whether this is possible in a faster way.

[Labdabeta]

I still do not believe that is what is desired here. What seems to be the goal is some function like vector<string> getAllPalindromes(string str) that returns all palindromes in a string. So for example, getAllPalindromes("No lemon, no melon!") should return {"nolemonnomelon","olemonnomelo",...,"onno","nn"}.

As far as I can tell there is no more efficient way to do this than to loop letter by letter and check each substring for palindromes.

IE:

vector<string> getAllPalindromes(string str)
{
    vector<string> ret;
    for (int i=0; i<str.length(); ++i)
    {
        for (int ii=str.length()-1; ii>(i+1); --ii)//the i+1 is to eliminate 1 letter palindromes
        {
            if (isPalindrome(str.substr(i,ii)))
            {
                //add the string, and all its inner strings to ret
                //so "kayak" would add "kayak", and "aya" to ret
                i=ii;//skip ahead to the end of that sub-palindrome
                //break; the inner loop should break itself anyways.
            }
        }
    }
    return ret;
}

[sepp2k]

Your code won't print all palindromes in all cases:

A palindrome can contain other palindromes that aren't its "inner strings". Take the string "kakykak" for example. Your algorithm will find "kakykak", "akyka" and "kyk", but not the two "kak"s.

Another problem is that palindromes can overlap. For example "akala" contains the palindromes "aka" and "ala", but your code wouldn't find the latter because after finding "aka", it would skip right to index 3 (the "l") and would not look for any palindromes starting at index 2.

Also technically every single letter of the string is a palindrome by itself, too.

As far as I can tell there is no more efficient way to do this

I'm assuming that the OP came across this problem in a programming contest or a site with a collection of algorithm problems or something of that sort (or possibly homework). And in those kinds of sites/contests, they wouldn't pose a problem that can't be solved in a reasonable amount of time (meaning O(n^2) at most usually). So for that reason alone I'd expect there to be a more efficient algorithm.

[vijayan121]

OP doesn't have an array of strings where he wants to check each element string. He has one string of which he wants to check every substring. Iterating over all possible substrings and calling is_palindrome on each of them (which is basically what the OP is doing now - albeit in a needlessly complicated -- and apparently in some cases broken -- way) leads to a O(n^3) runtime. The question is whether this is possible in a faster way.

Ah!

Googling for "Manacher's algorithm" (and then applying a simple enough extension to that algorithm) would lead one towards discovering an efficient solution.

A suffix tree based approch is an alternative. The algorithm is described in Gusfield's book. http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198