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.
