Re: [algogeeks] string matching problem
above link was for reference , extending the logic was obvious :) :) On Mon, Sep 3, 2012 at 11:22 AM, bharat b bagana.bharatku...@gmail.comwrote: @atul: question is to find the largest continuous sub array .. not just continuous sub array .. we can do this with same logic as mentioned in the above link.. we have to traverse whole array.. even if we get the solution .. whenever we get the solution,update the largest_subarray_start_index and largest_subarray_end_index based on previous length of the solution sub array . On Mon, Sep 3, 2012 at 9:26 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to 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. -- 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] string matching problem
why can't we change the question to sum=0 .. On Mon, Sep 3, 2012 at 12:57 PM, atul anand atul.87fri...@gmail.com wrote: above link was for reference , extending the logic was obvious :) :) On Mon, Sep 3, 2012 at 11:22 AM, bharat b bagana.bharatku...@gmail.comwrote: @atul: question is to find the largest continuous sub array .. not just continuous sub array .. we can do this with same logic as mentioned in the above link.. we have to traverse whole array.. even if we get the solution .. whenever we get the solution,update the largest_subarray_start_index and largest_subarray_end_index based on previous length of the solution sub array . On Mon, Sep 3, 2012 at 9:26 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to 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. -- 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] string matching problem
http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to 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] string matching problem
@atul: question is to find the largest continuous sub array .. not just continuous sub array .. we can do this with same logic as mentioned in the above link.. we have to traverse whole array.. even if we get the solution .. whenever we get the solution,update the largest_subarray_start_index and largest_subarray_end_index based on previous length of the solution sub array . On Mon, Sep 3, 2012 at 9:26 AM, atul anand atul.87fri...@gmail.com wrote: http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to 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. -- 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] string matching
Patrick!!! On Thu, Jun 23, 2011 at 11:29 AM, prateek gupta prateek00...@gmail.comwrote: yup, got it thanks!!! On Thu, Jun 23, 2011 at 11:27 AM, sunny agrawal sunny816.i...@gmail.comwrote: last line is *in worst case k=1 only 2*n comparisons will be there hence O(n)* On Thu, Jun 23, 2011 at 11:26 AM, sunny agrawal sunny816.i...@gmail.comwrote: Lets Consider the case of Naive matching in which at some shift s first k characters are matched and next character does not match so instead of starting from s+1 shift we can safely jump to s+k because all characters of pattern are distinct in worst case k=1 only an comparisons will be there hence O(n) On Thu, Jun 23, 2011 at 11:19 AM, Piyush Sinha ecstasy.piy...@gmail.com wrote: Read KMP algorithm.. On Thu, Jun 23, 2011 at 11:17 AM, prateek gupta prateek00...@gmail.com wrote: In naive string matching how can the knowledge abt. pattern that it has all different characters can be used to accelerate the algorithm to 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 -- 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. -- 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] string matching
String matching can be performed in linear time with KMP algorithm. could you say what more optimization you are looking for here? Sent from my Windows Phone -- From: prateek gupta Sent: 23/06/2011 11:17 To: algogeeks@googlegroups.com Subject: [algogeeks] string matching In naive string matching how can the knowledge abt. pattern that it has all different characters can be used to accelerate the algorithm to 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.
[algogeeks] string matching
In naive string matching how can the knowledge abt. pattern that it has all different characters can be used to accelerate the algorithm to 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.
Re: [algogeeks] string matching
Read KMP algorithm.. On Thu, Jun 23, 2011 at 11:17 AM, prateek gupta prateek00...@gmail.comwrote: In naive string matching how can the knowledge abt. pattern that it has all different characters can be used to accelerate the algorithm to 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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] string matching
last line is *in worst case k=1 only 2*n comparisons will be there hence O(n)* On Thu, Jun 23, 2011 at 11:26 AM, sunny agrawal sunny816.i...@gmail.comwrote: Lets Consider the case of Naive matching in which at some shift s first k characters are matched and next character does not match so instead of starting from s+1 shift we can safely jump to s+k because all characters of pattern are distinct in worst case k=1 only an comparisons will be there hence O(n) On Thu, Jun 23, 2011 at 11:19 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Read KMP algorithm.. On Thu, Jun 23, 2011 at 11:17 AM, prateek gupta prateek00...@gmail.comwrote: In naive string matching how can the knowledge abt. pattern that it has all different characters can be used to accelerate the algorithm to 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 -- 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] string matching
yup, got it thanks!!! On Thu, Jun 23, 2011 at 11:27 AM, sunny agrawal sunny816.i...@gmail.comwrote: last line is *in worst case k=1 only 2*n comparisons will be there hence O(n)* On Thu, Jun 23, 2011 at 11:26 AM, sunny agrawal sunny816.i...@gmail.comwrote: Lets Consider the case of Naive matching in which at some shift s first k characters are matched and next character does not match so instead of starting from s+1 shift we can safely jump to s+k because all characters of pattern are distinct in worst case k=1 only an comparisons will be there hence O(n) On Thu, Jun 23, 2011 at 11:19 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Read KMP algorithm.. On Thu, Jun 23, 2011 at 11:17 AM, prateek gupta prateek00...@gmail.comwrote: In naive string matching how can the knowledge abt. pattern that it has all different characters can be used to accelerate the algorithm to 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 -- 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. -- 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.
