yup, got it thanks!!!
On Thu, Jun 23, 2011 at 11:27 AM, sunny agrawal <[email protected]>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 > <[email protected]>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 >> <[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 >> >> > > > -- > 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. > -- 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.
