@varun : isn't the longest common subsequence abccba and longest common
substring is
abc or cba?in any case what is the longest palindrom in the given string
abcdecba?? isnt it the individual letters itself ie length max is 1?
On Wed, Jun 22, 2011 at 10:45 AM, varun gupta varun.gt...@gmail.com
@hary: nhin, its some constant multiple of n. O(constant*n)
for a string of length n, 2*n-1 positions are there.
every time i calculate the next center using prev center value
if the value at prev center is a large one then this next center value
skips that many positions to compensate..
if the
i have posted some time back but that is O(N) , need to code suffix
tree will do that asap i get the time.
Thanks
Shashank
CSE BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
sorry for typo that is O(N^2)
Thanks
Shashank
--
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
I don't think a O(n) solution exists... for each candidate string we
find, we'll still have to validate that its a palindrome right?
On Jul 1, 5:10 am, bittu shashank7andr...@gmail.com wrote:
sorry for typo that is O(N^2)
Thanks
Shashank
--
You received this message because you are
btw, they don't need a substring, but a subsequence.
On Thu, Jun 30, 2011 at 11:41 PM, Dumanshu duman...@gmail.com wrote:
heres the code: http://ideone.com/aiG1m
using the algo from
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
On Jun 21,
heres the code: http://ideone.com/aiG1m
using the algo from
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
On Jun 21, 11:31 pm, Swathi chukka.swa...@gmail.com wrote:
Does any one know how to return the Longest palindrome in a string in
O(n).
From
I know that is not the best solution but here we go:
p [i] [j] = 1 if s [i.. j] is palindrome, 0 otherwise
p [i] [i] = 1
p [i] [i +1] = s [i] == s [i +1]
p [i] [k] = s [i] == s [k] p [i +1] [k-1], k i +1
time complexity = O (n ^ 2)
Space complexity = O (n ^ 2)
You can modify the algorithm to
http://stevekrenzel.com/articles/longest-palnidrome
But for some reason it is failing for string ISAAS, may be my
understanding is incorrect.
Thanks
Avinash
http://avi-programming-blog.blogspot.com/
On Jun 21, 11:31 pm, Swathi chukka.swa...@gmail.com wrote:
Does any one know how to return the
http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html
On Wed, Jun 22, 2011 at 9:28 PM, Avinash dongre.avin...@gmail.com wrote:
http://stevekrenzel.com/articles/longest-palnidrome
But for some reason it is failing for string ISAAS, may be my
understanding is
couldn't we just collect all the letters that occur more than twice
and play them back even number of times symmetrically? and if there
are more letters left, we can put one of them in the center...
linear time need additional memory for some kind of hashing
On Jun 21, 11:31 am, Swathi
Suffix tree can solve longest common substring problem in o(n)
and longest palindrome in string S is nothing but longest common
substring between string s and its reverse.
On Wed, Jun 22, 2011 at 9:31 PM, ankit mehta mehta.bond...@gmail.com wrote:
You dont have to create longest palindrome,
Consider string: abcdecba
Reverse of above string: abcedcba
Longest common substring: abc and cba : Both not Palindromes!
On Jun 22, 9:29 pm, sanjay ahuja sanjayahuja.i...@gmail.com wrote:
Suffix tree can solve longest common substring problem in o(n)
and longest palindrome in string S is
LCS is abcdcba or abcecba
not abc or cba
On Wed, Jun 22, 2011 at 10:15 PM, ankit mehta mehta.bond...@gmail.comwrote:
Consider string: abcdecba
Reverse of above string: abcedcba
Longest common substring: abc and cba : Both not Palindromes!
On Jun 22, 9:29 pm, sanjay ahuja
Does the question mean non-continuous substring? I think it should be
continuous substring which is palindrome with in the given string. LCS
wouldn't solve problem in this case.
On Wed, Jun 22, 2011 at 10:29 PM, sunny agrawal sunny816.i...@gmail.comwrote:
LCS is abcdcba or abcecba
not abc or
LCS stands for Longest Common Substring
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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
That is what ankit said.
Consider string: abcdecba
Reverse of above string: abcedcba
Longest common substring: abc and cba :
you are calculating longest common *subsequence* not substring. Substring in
continuous.
On Wed, Jun 22, 2011 at 10:48 PM, sunny agrawal sunny816.i...@gmail.comwrote:
ah... i misunderstood the question... sorry..
On Jun 22, 12:01 pm, ankit mehta mehta.bond...@gmail.com wrote:
You dont have to create longest palindrome, you have to find the
longest palindrome.
On Jun 22, 7:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
couldn't we just collect
ohh sorry my mistake
LCS stands for Longest Common Subsequence
On Wed, Jun 22, 2011 at 11:21 PM, SVIX saivivekh.swaminat...@gmail.comwrote:
ah... i misunderstood the question... sorry..
On Jun 22, 12:01 pm, ankit mehta mehta.bond...@gmail.com wrote:
You dont have to create longest
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
This algo runs in Linear time.
On Thu, Jun 23, 2011 at 1:23 AM, sunny agrawal sunny816.i...@gmail.comwrote:
ohh sorry my mistake
LCS stands for Longest Common Subsequence
On Wed, Jun 22, 2011 at 11:21
20 matches
Mail list logo
