use stackpush one by one element before compare to top 2 element in stack {if
same then pop element and compare next char of string with top char in stackif
same continue otherwise clear stack}else{push element to stack}
if wrong correct me
--- On Sat, 21/8/10, nipun batra <[email protected]> wrote:
From: nipun batra <[email protected]>
Subject: Re: [algogeeks] Longest Palindromic Substring
To: [email protected]
Date: Saturday, 21 August, 2010, 4:18 PM
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:
@chonkuAs 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].
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.
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].
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.
--
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.
--
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.
