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...