Re: [algogeeks] O(n) solution is there or not!!
@Carl-At each step you are calculating lcp between the text and the last entry probably to compare ... lcp[i+1]..is it linear still -- 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] O(n) solution is there or not!!
@Atul- can you explain ur approach a little more..What is A and B string wd reference to question..for each A and B string it will take O(n) time to make the table...ur approach is O(n)..dont think so..please explain may be i m wrong -- 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] O(n) solution is there or not!!
@carl-Sorry was making suffix array by naive approx in the link http://en.wikipedia.org/wiki/Suffix_array .there are more optimized algos for it...!! 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] O(n) solution is there or not!!
Yeah sorry, misread the question then had a quick attempt :) I don't see where you get the lg n from though. I didn't do any binary searches. On 19 August 2012 22:53, pankajsingh psingh...@gmail.com wrote: @carl- got ur point..but complexity is more..suffix array takes o(n^2lgn)..considering string comparisons. complexity to build...i already have o(n^2)..want 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 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] O(n) solution is there or not!!
Thanks.carl and atul.!!.@carl-i got lgn due to string comparison sort while making the suffix array..:) -- 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] O(n) solution is there or not!!
I still don't understand. There's far quicker suffix array construction algorithms than O(n^2 log n)? There's O(n) algorithms On 20 August 2012 23:27, pankajsingh psingh...@gmail.com wrote: Thanks.carl and atul.!!.@carl-i got lgn due to string comparison sort while making the suffix array..:) -- 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] O(n) solution is there or not!!
Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh psingh...@gmail.com wrote: Is there any O(n) solution this question...I Cleared all the testcases but my solution is not O(n) and...I think there should be some O(n) solution..by seeing the constraint to this question..I tried to think for Kmp in this ..but didnt workand suffix array method will have more complexity..any suggestion For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings abc and abd is 2, while the similarity of strings aaa and aaab is 3. Calculate the sum of similarities of a string S with each of it's suffixes. *Input:* The first line contains the number of test cases T. Each of the next T lines contains a string each. *Output:* Output T lines containing the answer for the corresponding test case. *Constraints:* 1 = T = 10 The length of each string is at most 10 and contains only lower case characters. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] O(n) solution is there or not!!
Or a suffix tree would work. Pre process it to answer Lowest common ancestor queries. On 19 August 2012 21:51, Carl Barton odysseus.ulys...@gmail.com wrote: Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh psingh...@gmail.com wrote: Is there any O(n) solution this question...I Cleared all the testcases but my solution is not O(n) and...I think there should be some O(n) solution..by seeing the constraint to this question..I tried to think for Kmp in this ..but didnt workand suffix array method will have more complexity..any suggestion For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings abc and abd is 2, while the similarity of strings aaa and aaab is 3. Calculate the sum of similarities of a string S with each of it's suffixes. *Input:* The first line contains the number of test cases T. Each of the next T lines contains a string each. *Output:* Output T lines containing the answer for the corresponding test case. *Constraints:* 1 = T = 10 The length of each string is at most 10 and contains only lower case characters. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] O(n) solution is there or not!!
@Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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] O(n) solution is there or not!!
Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure. 1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called total with this value and another variable called last. Last is a variable to store the lcp between the text and the last suffix you considered. 3. Now traverse the suffix array using the lcp array. for some point, i, if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i+1] if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i-1] if the lcp between the text and the last entry is = lcp[i+1] you need to do some more work and try and extend the match from position lcp[i+1] I think that should be linear though? correctme if i'm wrong. On 19 August 2012 22:23, pankajsingh psingh...@gmail.com wrote: @Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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] O(n) solution is there or not!!
concatenate 2 strings adding wild character in between i.e A=aaa B=aaab A+B =aaa$aaab; wild character is $; now create longest prefix table(partial match table) as we do in KMP algo. now search for max value after $ index...in LPS table. I guess it would work On Sun, Aug 19, 2012 at 8:23 PM, Carl Barton odysseus.ulys...@gmail.comwrote: Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure. 1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called total with this value and another variable called last. Last is a variable to store the lcp between the text and the last suffix you considered. 3. Now traverse the suffix array using the lcp array. for some point, i, if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i+1] if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i-1] if the lcp between the text and the last entry is = lcp[i+1] you need to do some more work and try and extend the match from position lcp[i+1] I think that should be linear though? correctme if i'm wrong. On 19 August 2012 22:23, pankajsingh psingh...@gmail.com wrote: @Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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] O(n) solution is there or not!!
@carl- got ur point..but complexity is more..suffix array takes o(n^2lgn)..considering string comparisons. complexity to build...i already have o(n^2)..want 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
