Re: [algogeeks] Re: Amazon - Longest palindrome in a string in O(n)
@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 wrote: 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: 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 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. -- Warm Regards, Varun Kumar Email Id: varun.gt...@gmail.com Contact: +91-9711751235 -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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, 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 googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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. -- Regards, Arpit Sood -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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 use only O (n) space using only the diagonal matrix Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jun 23, 2011 at 1:06 PM, Anand anandut2...@gmail.com wrote: 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 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 Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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 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 Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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, you have to find the longest palindrome. On Jun 22, 7:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote: 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 chukka.swa...@gmail.com wrote: Does any one know how to return the Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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. -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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 sanjayahuja.i...@gmail.com wrote: 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, you have to find the longest palindrome. On Jun 22, 7:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote: 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 chukka.swa...@gmail.com wrote: Does any one know how to return the Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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 athttp:// groups.google.com/group/algogeeks?hl=en. -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd -- 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. -- 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 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] Re: Amazon - Longest palindrome in a string in O(n)
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 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 sanjayahuja.i...@gmail.com wrote: 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, you have to find the longest palindrome. On Jun 22, 7:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote: 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 chukka.swa...@gmail.com wrote: Does any one know how to return the Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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 athttp:// groups.google.com/group/algogeeks?hl=en. -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd -- 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. -- 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 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. -- Warm Regards, Varun Kumar Email Id: varun.gt...@gmail.com Contact: +91-9711751235 -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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 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] Re: Amazon - Longest palindrome in a string in O(n)
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: 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 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. -- Warm Regards, Varun Kumar Email Id: varun.gt...@gmail.com Contact: +91-9711751235 -- 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] Re: Amazon - Longest palindrome in a string in O(n)
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 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 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 chukka.swa...@gmail.com wrote: Does any one know how to return the Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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. -- 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 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] Re: Amazon - Longest palindrome in a string in O(n)
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 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 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 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 chukka.swa...@gmail.com wrote: Does any one know how to return the Longest palindrome in a string in O(n). From googling i found that we can use suffix trees but there is no code. I am looking for logic and also for running code. Thanks, Swathi -- 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. -- 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 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. -- Abhishek Agrawal +919533890833 -- 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.
