1)maintain 2 pointers.. one from left and other from right.. 2)run two nested loops to compre each element from right with the element in left..
3)if they are same pass the subset(the characters in between) to function that checks if it is a palindrome or not. complexity==> O(n^2)+O(n) correct me if am wrong On Sun, Aug 22, 2010 at 5:48 AM, venkatesan B <[email protected] > wrote: > use stack > push 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 > stack > if 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]<http://mc/[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]<http://mc/[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]<http://mc/[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]<http://mc/[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] > <http://mc/[email protected]>. > > To unsubscribe from this group, send email to > [email protected] > <http://mc/compose?to=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]<http://mc/[email protected]> > . > To unsubscribe from this group, send email to > [email protected]<http://mc/compose?to=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] > <http://mc/[email protected]>. > > To unsubscribe from this group, send email to > [email protected] > <http://mc/compose?to=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]<http://mc/[email protected]> > . > To unsubscribe from this group, send email to > [email protected]<http://mc/compose?to=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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- thanks and regards aravind prasad -- 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.
