Re: [algogeeks] longest palindrome in a string size 2*10^4

[Aditya Raman]

@rahul: excellent answer. thanks a ton!!.
@navin :i will try that too .Thanks !!

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

Re: [algogeeks] longest palindrome in a string size 2*10^4

[SHOBHIT GUPTA]

http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html:
linear time

On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman wrote:

> Hello everybody,
> I need to find a way of finding the longest palindrome in a very very long
> string (n<=2) . a linear time algo is expected. help me out
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/JdXOBU9fu34J.
> To post to this group, send email to algogeeks@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.
>

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

Re: [algogeeks] longest palindrome in a string size 2*10^4

[Rahul Kumar Dubey]

 *Manacher's algorithm *
*
*
*Its a famous algorithm for finding longest palindrome in a string in O(n)*
*have a look at it on internet ...*
*http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html*
see if it can help you ..

On Sun, Sep 23, 2012 at 5:29 PM, Navin Kumar wrote:

> " *Ukkonen's algorithm* is a linear-time, online 
> algorithmfor constructing 
> suffix
> trees , proposed by Esko 
> Ukkonenin
>  1995"
>
> source: wikipedia
>
>
> On Sun, Sep 23, 2012 at 5:08 PM, Navin Kumar wrote:
>
>> Build a common suffix tree for the given string and for its reverse. Then
>> take out the string ending at maximum depth at a common node. Time
>> complexity would be linear.
>>
>> On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman > > wrote:
>>
>>> Hello everybody,
>>> I need to find a way of finding the longest palindrome in a very very
>>> long string (n<=2) . a linear time algo is expected. help me out
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/JdXOBU9fu34J.
>>> To post to this group, send email to algogeeks@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.
>>>
>>
>>
>  --
> 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.
> 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.
>



-- 
*RAHUL KUMAR DUBEY*
*BTech-3rd  year *
*Computer Science &Engineering *
*Motilal Nehru National Institute Of Technology*
*Allahabad[211004],UP.*

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

Re: [algogeeks] longest palindrome in a string size 2*10^4

[Navin Kumar]

" *Ukkonen's algorithm* is a linear-time, online
algorithmfor
constructing suffix
trees , proposed by Esko
Ukkonenin
1995"

source: wikipedia

On Sun, Sep 23, 2012 at 5:08 PM, Navin Kumar wrote:

> Build a common suffix tree for the given string and for its reverse. Then
> take out the string ending at maximum depth at a common node. Time
> complexity would be linear.
>
> On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman 
> wrote:
>
>> Hello everybody,
>> I need to find a way of finding the longest palindrome in a very very
>> long string (n<=2) . a linear time algo is expected. help me out
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/JdXOBU9fu34J.
>> To post to this group, send email to algogeeks@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.
>>
>
>

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

Re: [algogeeks] longest palindrome in a string size 2*10^4

[Navin Kumar]

Build a common suffix tree for the given string and for its reverse. Then
take out the string ending at maximum depth at a common node. Time
complexity would be linear.

On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman wrote:

> Hello everybody,
> I need to find a way of finding the longest palindrome in a very very long
> string (n<=2) . a linear time algo is expected. help me out
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/JdXOBU9fu34J.
> To post to this group, send email to algogeeks@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.
>

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

Re: [algogeeks] Longest palindrome

[hary rathor]

you can do it in O(n) if you can give extra memory O(n).

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

Re: [algogeeks] Longest palindrome

[Victor Manuel Grijalva Altamirano]

Use DP, read the algorithm "Edit distance" and modificated to get max palim.


2011/8/21 anurag saxena 

> method 1) : we can reverse the string and find the longest common
> substring occurring in reversed string and original string.
>
> method 2) : making a generalized suffix tree of string and reversed
> string and each node should depict whether the suffix  belongs to
> string or reversed string .. then the deepest node having both the
> marker will be longest palindrome.
>
> On 8/21/11, Sanjay Rajpal  wrote:
> > i hvn't read about suffix trees. will u plz post a useful link ?
> >
> >
> > Sanju
> > :)
> >
> >
> >
> > On Sun, Aug 21, 2011 at 11:21 AM, MAC  wrote:
> >
> >> suffix tree will solve it .
> >>
> >>
> >> On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh <
> >> love.for.programm...@gmail.com> wrote:
> >>
> >>> how abt goimg with brute force?? check  starting from first character
> if
> >>> first 2 chars frm a palin, then chck if first 3 form a palin...
> continue
> >>> until the end of string.
> >>>
> >>> Now starting from 2nd char, do the same.
> >>>
> >>> keep a var max to store the max value.
> >>>
> >>> --
> >>> 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.
> >>> 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.
> >>>
> >>
> >>
> >>
> >> --
> >> thanks
> >> --mac
> >>
> >>
> >> --
> >> 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.
> >> 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.
> >>
> >
> > --
> > 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.
> > 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.
> >
> >
>
> --
> 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.
> 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.
>
>


-- 
Victor Manuel Grijalva Altamirano
Universidad Tecnologica de La Mixteca

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

Re: [algogeeks] Longest palindrome

[anurag saxena]

method 1) : we can reverse the string and find the longest common
substring occurring in reversed string and original string.

method 2) : making a generalized suffix tree of string and reversed
string and each node should depict whether the suffix  belongs to
string or reversed string .. then the deepest node having both the
marker will be longest palindrome.

On 8/21/11, Sanjay Rajpal  wrote:
> i hvn't read about suffix trees. will u plz post a useful link ?
>
>
> Sanju
> :)
>
>
>
> On Sun, Aug 21, 2011 at 11:21 AM, MAC  wrote:
>
>> suffix tree will solve it .
>>
>>
>> On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh <
>> love.for.programm...@gmail.com> wrote:
>>
>>> how abt goimg with brute force?? check  starting from first character if
>>> first 2 chars frm a palin, then chck if first 3 form a palin... continue
>>> until the end of string.
>>>
>>> Now starting from 2nd char, do the same.
>>>
>>> keep a var max to store the max value.
>>>
>>> --
>>> 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.
>>> 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.
>>>
>>
>>
>>
>> --
>> thanks
>> --mac
>>
>>
>> --
>> 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.
>> 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.
>>
>
> --
> 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.
> 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.
>
>

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

Re: [algogeeks] Longest palindrome

[saurabh modi]

dp will work fine. :-)
O(n^2) algo.

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

Re: [algogeeks] Longest palindrome

[Sanjay Rajpal]

i hvn't read about suffix trees. will u plz post a useful link ?


Sanju
:)



On Sun, Aug 21, 2011 at 11:21 AM, MAC  wrote:

> suffix tree will solve it .
>
>
> On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh <
> love.for.programm...@gmail.com> wrote:
>
>> how abt goimg with brute force?? check  starting from first character if
>> first 2 chars frm a palin, then chck if first 3 form a palin... continue
>> until the end of string.
>>
>> Now starting from 2nd char, do the same.
>>
>> keep a var max to store the max value.
>>
>> --
>> 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.
>> 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.
>>
>
>
>
> --
> thanks
> --mac
>
>
> --
> 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.
> 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.
>

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

Re: [algogeeks] Longest palindrome

[MAC]

suffix tree will solve it .

On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh <
love.for.programm...@gmail.com> wrote:

> how abt goimg with brute force?? check  starting from first character if
> first 2 chars frm a palin, then chck if first 3 form a palin... continue
> until the end of string.
>
> Now starting from 2nd char, do the same.
>
> keep a var max to store the max value.
>
>  --
> 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.
> 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.
>



-- 
thanks
--mac

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

Re: [algogeeks] Longest palindrome

[priya ramesh]

how abt goimg with brute force?? check  starting from first character if
first 2 chars frm a palin, then chck if first 3 form a palin... continue
until the end of string.

Now starting from 2nd char, do the same.

keep a var max to store the max value.

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

Re: [algogeeks] Longest Palindrome

[Rishi Agrawal]

The blogsite referred is unavailable.


On Fri, Dec 31, 2010 at 3:49 AM, Anand  wrote:

>
> http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html
>
>
> On Thu, Dec 30, 2010 at 1:10 PM, Aniket  wrote:
>
>> How do you find the longest palindrome in a given string in O(n) time?
>>
>> --
>> 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.
>>
>>
>  --
> 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.
>



-- 
Regards,
Rishi Agrawal

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

Re: [algogeeks] Longest Palindrome

[Anand]

http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html

On Thu, Dec 30, 2010 at 1:10 PM, Aniket  wrote:

> How do you find the longest palindrome in a given string in O(n) time?
>
> --
> 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.
>
>

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

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

[Amit Jaspal]

I don't understand how to constuct the suffix tree in less than O(n^2) can
anyone explain me this?

On Tue, Jul 6, 2010 at 10:03 AM, Jitendra Kushwaha  wrote:

> @Ankit Narang
>   Think about your algo it is not a O(n). First of all you wont get
> solution comparing start of str1 and end of str2
>
> Their is solution in O(n) other than suffix tree
> Here is the link
>
> http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
>
> --
> Regards
> Jitendra Kushwaha
> MNNIT, Allahabad
>
> --
> 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.
>

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

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

[Jitendra Kushwaha]

@Ankit Narang
  Think about your algo it is not a O(n). First of all you wont get solution
comparing start of str1 and end of str2

Their is solution in O(n) other than suffix tree
Here is the link
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

-- 
Regards
Jitendra Kushwaha
MNNIT, Allahabad

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

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

[Ashish Goel]

refer

http://www.allisons.org/ll/AlgDS/Tree/Suffix/

this would be at most O(n)


Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Mon, Jul 5, 2010 at 10:45 PM, vijay  wrote:

> Longest palindrome in a given str (less than O(n^2) )
>
> i think we should use suffix tree. does anyone know the algo\logic?
>
> --
> 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.
>
>

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

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

[jalaj jaiswal]

make a generalised suffix tree of str and reverse of str
then for every two nodes find the longest common prefix

On Mon, Jul 5, 2010 at 10:45 PM, vijay  wrote:

> Longest palindrome in a given str (less than O(n^2) )
>
> i think we should use suffix tree. does anyone know the algo\logic?
>
> --
> 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.
>
>


-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

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