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 <[email protected]>wrote: > > Read KMP algorithm.. > > > On Thu, Jun 23, 2011 at 11:17 AM, prateek gupta <[email protected]>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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
