An O(n^3) solution.Wanna know if it's possible to optimize without using
trees.
#include<iostream>
#include<string.h>
using namespace std;
char* substring(char*s,int start,int finish)
{
int ctr=0;
char str[1000];
while(start<=finish)
{
str[ctr]=s[start];
start+=1;
ctr+=1;
}
str[ctr]='\0';
return str;
}
bool isPalindrome(char *s)
{
int size=strlen(s);
int j=size-1;
int i=0;
while((s[i]==s[j])&&(i<j))
{
i+=1;
j-=1;
}
if (i>=j)
return true;
else
return false;
}
int main()
{
int i,j;
char s[100];
cin>>s;
int size=strlen(s);
int tempMax=size-1;
while(tempMax>1)
{
for(i=0;i+tempMax<size;i++)
{
if(isPalindrome(substring(s,i,i+tempMax)))//O(n)
{
puts(substring(s,i,i+tempMax));
cout<<" of size "<<tempMax<<"\n";
break;
}
}
tempMax-=1;
}
return 0;
}
On Sat, Aug 21, 2010 at 12:12 PM, Chonku <[email protected]> wrote:
> I definitely meant a suffix Tree and not a trie. Apologize for that. :)
>
> On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal <[email protected]>wrote:
>
>> @chonku
>> As i understand, a trie is used when we have a lot of strings (such as a
>> dictionary).
>> Here we just have a single string. The resultant trie will be:
>>
>> a
>> \
>> b
>> \
>> c
>> \
>> l
>> \
>> e
>> \
>> v
>> \
>> e
>> \
>> l
>> \
>> a
>> \
>> b
>> \
>> c
>>
>> We get a similar trie for the reverse string.
>>
>> So why are you using a trie here? I cant see any advantage of it here.
>>
>> On Fri, Aug 20, 2010 at 8:36 AM, Chonku <[email protected]> wrote:
>>
>>> Can we use a trie here.
>>> Make first pass from left to right and construct the trie.
>>> Make second pass from right to left and look for the trie branch with
>>> maximum nodes that match the characters.
>>>
>>> On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal <[email protected]
>>> > wrote:
>>>
>>>> Hi All,
>>>>
>>>> Givan a string, you have to find the longest palindromic substring.
>>>> For ex: Longest Palindromic substring for abclevelabc is level.
>>>>
>>>> What is the most optimised solution possible?
>>>>
>>>> Please access the attached hyperlink for an important electronic
>>>> communications disclaimer:
>>>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>>
>>>> You received this message because you are subscribed to the Google Groups
>>>> "Algorithm Geeks" group.
>>>>
>>>> To post to this group, send email to [email protected].
>>>>
>>>> To unsubscribe from this group, send email to
>>>> [email protected]
>>>> <algogeeks%[email protected]>.
>>>>
>>>>
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> Please access the attached hyperlink for an important electronic
>> communications disclaimer:
>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>>
>>
>>
>> --
>>
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>>
>> To post to this group, send email to [email protected].
>>
>> To unsubscribe from this group, send email to
>> [email protected]
>> <algogeeks%[email protected]>.
>>
>>
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
