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
*Ukkonen's algorithm* is a linear-time, online
algorithmhttp://en.wikipedia.org/wiki/Online_algorithmfor
constructing suffix
trees http://en.wikipedia.org/wiki/Suffix_tree, proposed by Esko
Ukkonenhttp://en.wikipedia.org/w/index.php?title=Esko_Ukkonenaction=editredlink=1in
1995
source: wikipedia
*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
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 adityarareloa...@gmail.comwrote:
Hello everybody,
I need to find a way of finding the longest palindrome in a very very long
string (n=2) . a linear time
@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
while suffix tree of str and reverse(str) and finding deepst fork to get
the palindrome works, there is a solution available at
http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html
which is O(n). Can anyone explain this, a bit complex for me.
Best Regards
Ashish Goel
Think positive
Suggest a method to find longest palindrome in a given string..
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
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
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
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 macatad...@gmail.com 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
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
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
Use DP, read the algorithm Edit distance and modificated to get max palim.
2011/8/21 anurag saxena anurag.saxen...@gmail.com
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
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
Can Anyone help me in understanding how to find longest palindrome in a
given String
i tried to read the same from the following link
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
but couldn't understand what the algo is actually..can someone
The blogsite referred is unavailable.
On Fri, Dec 31, 2010 at 3:49 AM, Anand anandut2...@gmail.com wrote:
http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html
On Thu, Dec 30, 2010 at 1:10 PM, Aniket aniket...@gmail.com wrote:
How do you find the longest
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
http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html
On Thu, Dec 30, 2010 at 1:10 PM, Aniket aniket...@gmail.com 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
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 jitendra.th...@gmail.com
wrote:
@Ankit Narang
Think about your algo it is not a O(n). First of all you wont get
solution comparing start of
@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/
--
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
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 auvija...@gmail.com wrote:
Longest palindrome in a given str (less than O(n^2) )
i think we should use suffix tree. does anyone know the
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 auvija...@gmail.com wrote:
Longest palindrome in a given str (less than O(n^2)
23 matches
Mail list logo