New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Adele Schaden MD


Adele Schaden MD
GPA 3.88

Tao Jiang

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Tao Jiang
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 7 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 141 at University of California Riverside taught by Tao Jiang in Fall. Since its upload, it has received 15 views. For similar materials see /class/231740/cs-141-university-of-california-riverside in ComputerScienence at University of California Riverside.

Similar to CS 141 at UCR

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
11 Sfring Search The goal is To find The firsT occurrence of a paTTern P of lengTh m in a TeXT T of lengTh n PaTTern P and TeXT T can be sequences of any kind noT necessarily characTer sequences found39 3 i I 1s i sn m1 maTchim A found39 1s i39 s n m 1A maTchi39m A nomaTchi39 1 where maTchik P1k nomaTchi V i I 1 Tiik 1 g k g i umaTchim ChapTer 34 in CLR presenTs Three algoriThms Naive KnuTh Morris PraTT Boyer Moore using The Theory of finiTe sTaTe machines Here we parle follow an alTernaTive presenTaTion of WirTh AlgoriThms and DaTa STrucTures PrenTice Hall 1986 pp 56 69 A copy of ThaT parT of The book is in The library I Naive Sfring Search The mosT sTraighTforward souTion is To sTarT comparing P wiTh T aT posiTion 1 and in case of mismaTch shifT The posiTion of P 1 2 I Ti ITM ITMHI I Tquot I 1 i e O found e false while found A i m s n do D invarianT nomaTchi i e i 1 found e maTchi m For The invarianT we observe ThaT nomaTchO holds iniTially and ThaT nomaTchi 1 and umaTchim implies nomaTchi The loop TerminaTes wiTh The posTcondiTion assuming m s n nomaTchi A found A im gt n v found A im s nA maTchim 178 Naive Sfring Search The sTaTemenT found e maTchim needs To be refined To a loop i e O found e false while found i m s n do D invarianT nomaTchi i lt i 1 J39 e 0 while lt mAPJ1 Tij do D invarianT maTchij 179 Analysis of Naive Sfring Search In The average case if The characTers are drawn from an alphabeT wiTh Two or more characTers and occur randomly we can expecT a mismaTch afTer less Than Two comparisons cf analysis of Table search and linear search and CRL exercise 341 4 Hence an upper bound of The average number of comparisons is 2 n m 1 which makes an average case running Time of On m For The worsT case suppose P consisTs of m 1 characTers quotaquot followed by characTer quotbquot and T consisTs of n characTers quotaquot or T consisTs of n 1 characTers quotaquot followed by quotbquot In boTh cases n m 1 m comparisons are necessary making a running Time of n m 1 m Improving Naive Sfr ing Search The idea is To use The informa rion provided by a par rial ma rch To avoid furTher comparisons which canno r possiny succeed TeXT c PaTTern Sh if red PaTTern Shif red Again TeXT PaTTern Sh if red PaTTern g EE 181 Improving Naive Sfr ing Search TeXT PaTTern Sh if red PaTTern Shif red Again TeXT PaTTern Sh if red PaTTern nun l 182 Sfrucfure of KnuTh Morris Pra Search i T lull P I ll AT each posiTion i in The TeXT T we compare Ti wiTh one or more elemenTs of P The index i used for comparisons wiTh Ti is eiTher incremenTed by one or remains The same iT is never decremenTed The indexj used for comparisons wiTh PJ391 is eiTher incremenTed by one or decremenTed by a value such ThaT iT becomes greaTer Than or equal To zero Sfrucfure of KnuTh Morris Pra Search The ouTer loop is responsible for incremenTing i by one and in case of a maTch incremenTingj by one The inner loop is responsible for shifTing P To The righT if possible i e O J39 e O whilejltmAiltndo D invarianT nomaTchi J39 maTchi j1j ie i1 whileJ39 gt O Pj1 Ti do Jlt if PJ391 Ti Then Je l found e j m D is sTill unspecified However we noTe ThaT if D lt J39 Then The assignmenTj e D will shifT P To The rigth If D 0 Then The paTTern is shifTed beyond iTs currenT posiTion Defermining Maximal Shiffs l The idea of D is ThaT iT depends only on The paTTern P and The posiTion j where 1 s J39s m Hence iT can be represenTed by D dJ39 where d is an array of Type d array 1m of inTeger For example for P quotababcquot we have for Pababa quQdm1Qd51Ldezqwo In general dJ39 is The lengTh of The longesT prefix of P1J39 which is also a suffix of P1j dJ39 maxk I O s k lt jA P1k Pj k1j CompuTing d amounTs To searching sTrings for which we can use KnuTh Morris PraTT search iTself l KnuTh Morris Pra Search D compuTe d d1 lt O k lt O for j e 2 To rn while k gt O Pk1 PJ39 do k lt dk if Pk1 PJ39 Then k lt k1 dJ39 lt k D search for P i e O J39 e O whilejltmAiltndo ie i1 whileJ39 gt O Pj1 Ti do i dJ39 if PJ391 Ti Then Jerl found e j m 186 Principle of Boyer Moore Search KnuTh Morris PraTT search yields a genuine benefiT only in The case of a parTial mismaTch which is comparaTively rare Boyer Moore Search improves also The average case The idea is To sTarT comparing The paTTern wiTh The TeXT aT The end of The paTTern In case of a mismaTch The paTTern can immediaTely be shifTed To The righT by a precompuTed number of posiTions Example where The compared characTers are underlined HoolaiHoola girls like Hooligans Hooligag Hooligag Hooligag Hooligag Hooligan Sfrucfure of Boyer Moore Search l LeT maTchij mean ThaT when P1 is shifTed over Ti Then all elemenTs To The righT of PJ39 maTch The corresponding ones in T leT nomaTchi mean ThaT There is no compleTe maTch up To Ti maTchi j PJ39 1 m Ti j i m 1 nomaTchi V kl 1s k s i umaTchi 0 iem while i s ndo D invarianT nomaTchi m je m k lt i while J39 gt O PJ39 Tk do D invarianT maTchi m 1 J i m k j je j 1 k lt k 1 ifj 0 Then reTurn k1 i lt i dTi Maximal Shiffs dX is defined To be The righTmosT occurrence of characTer X in P from The end noT including The IasT characTer VkIm dXltkltmPk X For example if P quotabcquot Then da zldb1dc 3 dx 3 for all X a b c If P quotaabquot Then da 1 db 3 dX 3 for all X 0 b If P quotabaquot Then da 2 db 1 dX 3 for all X 0 b Boyer Moore Search Boyer Moore Search P T for each characTer X do dXltI n for jelTom ldo dPiJ39JJemJ iern while i gndo Jlt rn k lt i whileJ39 gt O PJ39 Tk do JeJ1kek1 Whatisthebest if J O The and worst case refum k 1 running time i lt i dTi


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.