### Create a StudySoup account

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

Already have a StudySoup account? Login here

# INTERMED DATA STRUCS & ALGORITHM CS 141

UCR

GPA 3.88

### View Full Document

## 15

## 0

## 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.

## Reviews for INTERMED DATA STRUCS & ALGORITHM

### 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

### 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

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

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

#### "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."

#### "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."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.