@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 wrote:
> That is what a
btw, they don't need a substring, but a subsequence.
On Thu, Jun 30, 2011 at 11:41 PM, Dumanshu 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, 11:31 pm, Swat
@Dumanshu; worst case O(n3) hai iska
--
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 m
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
http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html
On Wed, Jun 22, 2011 at 9:28 PM, Avinash wrote:
> http://stevekrenzel.com/articles/longest-palnidrome
> But for some reason it is failing for string "ISAAS", may be my
> understanding is incorrect.
>
>
> Thanks
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 wrote:
> ohh sorry my mistake
> LCS stands for Longest Common Subsequence
>
>
> On Wed, Jun 22, 2011 at 11:21 PM, SVIX wrote:
>
ohh sorry my mistake
LCS stands for Longest Common Subsequence
On Wed, Jun 22, 2011 at 11:21 PM, SVIX wrote:
> ah... i misunderstood the question... sorry..
>
> On Jun 22, 12:01 pm, ankit mehta wrote:
> > You dont have to create longest palindrome, you have to find the
> > longest palindrome.
>
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 wrote:
> LCS stands for Longest
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 unsubscri
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 wrote:
> LCS is abcdcba or abcecba
> not abc or cba
>
>
> On Wed, Jun 2
LCS is abcdcba or abcecba
not abc or cba
On Wed, Jun 22, 2011 at 10:15 PM, ankit mehta wrote:
> 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 wrote:
> > Suffix tree can solve long
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 wrote:
> You dont have to create longest palindrome, you have to find the
> lo
12 matches
Mail list logo