@Aravind:
Ur soln will be O(n^2)*O(n).
It is similar to nipun's soln.
On Sun, Aug 22, 2010 at 6:15 AM, aravind prasad <raja....@gmail.com> wrote:
> 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 <
> venkat_b_engin...@yahoo.co.in> 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 <nipunredde...@gmail.com>* wrote:
>>
>>
>> From: nipun batra <nipunredde...@gmail.com>
>> Subject: Re: [algogeeks] Longest Palindromic Substring
>> To: algogeeks@googlegroups.com
>> 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
>> <cho...@gmail.com<http://mc/compose?to=cho...@gmail.com>
>> > 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
>> <fundoon...@yahoo.co.in<http://mc/compose?to=fundoon...@yahoo.co.in>
>> > 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
>> <cho...@gmail.com<http://mc/compose?to=cho...@gmail.com>
>> > 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
>> <fundoon...@yahoo.co.in<http://mc/compose?to=fundoon...@yahoo.co.in>
>> > 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 algogeeks@googlegroups.com
>> <http://mc/compose?to=algoge...@googlegroups.com>.
>>
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> <http://mc/compose?to=algogeeks%2bunsubscr...@googlegroups.com>.
>>
>>
>> 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
>> algogeeks@googlegroups.com<http://mc/compose?to=algoge...@googlegroups.com>
>> .
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<http://mc/compose?to=algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 algogeeks@googlegroups.com
>> <http://mc/compose?to=algoge...@googlegroups.com>.
>>
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> <http://mc/compose?to=algogeeks%2bunsubscr...@googlegroups.com>.
>>
>>
>> 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
>> algogeeks@googlegroups.com<http://mc/compose?to=algoge...@googlegroups.com>
>> .
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<http://mc/compose?to=algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
