Re: [algogeeks] Re: Longest Palindromic Substring
The question would be complete if we know what order of notation is needed for solution. On 23.08.2010 15:32, Chi Hoang wrote: I don't think so, I've have wriiten a kart-trie: http://sourceforge.net/projects/kart-trie which is basically a patricia-tree or radix-tree. Such a tree has maximum 2 leafs at each branch whilst a suffix-tree can has more then 2 leafs at each branch (BTW. can you explain to me what does edge means when talking about trees?). This is my understanding of a suffix-tree so far. I'm awaiting your anwser! 2010/8/21 Chonku cho...@gmail.com mailto:cho...@gmail.com You use a trie when you want to model a number of strings. Suffix Tree is used only when you have one string in your model. Suffix Tree is a type of trie, but the difference lies in the intent. On Sat, Aug 21, 2010 at 7:22 PM, Chi c...@linuxdna.com mailto:c...@linuxdna.com wrote: Isn't that by definition a compressed trie, i.e patricia-tree, crit- bit tree (suffix-tree)? Or what is the difference? On Aug 20, 5:17 pm, Nikhil Jindal fundoon...@yahoo.co.in mailto:fundoon...@yahoo.co.in wrote: @chonku As i understand, a trie is used when we have a lot of strings (such as a dictionary). Here we just have a single string. The resultant trie will be: a \ b \ c \ l \ e \ v \ e \ l \ a \ b \ c We get a similar trie for the reverse string. So why are you using a trie here? I cant see any advantage of it here. On Fri, Aug 20, 2010 at 8:36 AM, Chonku cho...@gmail.com mailto:cho...@gmail.com wrote: Can we use a trie here. Make first pass from left to right and construct the trie. Make second pass from right to left and look for the trie branch with maximum nodes that match the characters. On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal fundoon...@yahoo.co.in mailto:fundoon...@yahoo.co.inwrote: Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com mailto:toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com mailto:toalgogeeks%2bunsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com mailto:algogeeks%252bunsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en 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 toalgoge...@googlegroups.com mailto:toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are
Re: [algogeeks] Re: Array Problem
can you please explain more in detail the logic for XORing the index. On 22.08.2010 07:53, UMarius wrote: @Nikhil : I considered the array to be a linked list. xoring the indexes helps when you don't know how many elements you have. Marius. On Aug 22, 5:04 am, Nikhil Agarwalnikhil.bhoja...@gmail.com wrote: @marius Why are you xorring the indexes along with nos.?any special reason? On Sun, Aug 22, 2010 at 7:19 AM, UMariusmar...@aseara.ro wrote: @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1} the output is correct. Maybe I didn't explain the steps correctly. This is the code: for(int i = 0 ; i arr1.Length ; i++) { arr1XOR ^= arr1[i]; arr1XOR ^= i; arr1SUM += arr1[i]; arr1MUL *= arr1[i]; } for (int i = 0; i arr2.Length; i++) { arr2XOR ^= arr2[i]; arr2XOR ^= i; arr2SUM += arr2[i]; arr2MUL *= arr2[i]; } if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL == arr2MUL) { //SAME VALUES - IDENTICAL ARRAYS } else { //NOT IDENTICAL } Please correct me if I'm wrong. Marius. On Aug 22, 3:45 am, Davedave_and_da...@juno.com wrote: @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the original problem, you see that the question is not whether the arrays are identical (which is easily determined by simply comparing them element-by-element in O(n)), but whether they contain the same values, possibly in a different order. Dave On Aug 21, 11:01 am, UMariusmar...@aseara.ro wrote: What about this? 1. xor all elements of each array and their corresponding indexes sum all the elements of each array mul all elements of each array 2. if all results are the same then the arrays are identical Nice to meet you all, I just joined and this is my first post :) ... Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space?- Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd -- 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.