Patrick!!! On Thu, Jun 23, 2011 at 11:29 AM, prateek gupta <prateek00...@gmail.com>wrote:
> yup, got it thanks!!! > > > On Thu, Jun 23, 2011 at 11:27 AM, sunny agrawal > <sunny816.i...@gmail.com>wrote: > >> 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.com>wrote: >> >>> 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=100000655377926 * >>>> >>>> -- >>>> 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.
