STRINGS AND PATTERN MATCHING - Purdue University

1 1 STRINGS and PATTERN MatchingSTRINGS ANDPATTERNMATCHING Brute Force, Rabin-Karp, Knuth-Morris-PrattWhat s up?I m looking for some s quite a trick consideringthat you have no yeah? Have you seen your writing?It looks like an EKG!2 STRINGS and PATTERN MatchingString Searching The previous slide is not a great example of what ismeant by String Searching. Nor is it meant toridicule people without The object ofstring searching is to find the locationof a specific text PATTERN within a larger body of text( , a sentence, a paragraph, a book, etc.)

2 As with most algorithms, the main considerationsfor string searching are speed and efficiency. There are a number of string searching algorithms inexistence today, but the two we shall review areBrute Force and PATTERN MatchingBrute Force TheBrute Force algorithm compares the PATTERN tothe text, one character at a time, until unmatchingcharacters are found:- Compared characters are Correct matches are in boldface type. The algorithm can be designed to stop on either thefirst occurrence of the PATTERN , or upon reaching theend of the ROADS DIVERGED IN A YELLOW WOODROADSTWO ROADS DIVERGED IN A YELLOW WOODROADSTWO ROADS DIVERGED IN A YELLOW WOODROADSTWO ROADS DIVERGED IN A YELLOW WOODROADSTWOROADS DIVERGED IN A YELLOW WOODROADS4 STRINGS and PATTERN MatchingBrute Force Pseudo-Code Here s the pseudo-codedoif (text letter == PATTERN letter )

3 Compare next letter of PATTERN to nextletter of textelsemove PATTERN down text by one letterwhile (entire PATTERN found or end of text)tetththeheehthtehtheththehehthtthet etththeheehthtehtheththehehthtthetetthth eheehthtehtheththehehthtthetetththeheeht htehtheththehehthtthetetththeheehthtehth eththehehthtthetetththeheehthtehtheththe hehthtthe5 STRINGS and PATTERN MatchingBrute Force-Complexity Given a PATTERN M characters in length, and a text Ncharacters in Worst case: compares PATTERN to each substring oftext of length M.

4 For example, M= )AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made2)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made3)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made4)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made5)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons ) AAAAAAAAAAAAAAAAAAAAAAAAAAAH5 comparisons madeAAAAH Total number of comparisons: M (N-M+1) Worst case time complexity: (MN)6 STRINGS and PATTERN MatchingBrute Force-Complexity(cont.) Given a PATTERN M characters in length, and a text Ncharacters in Best case if PATTERN found: Finds PATTERN in first Mpositions of text.

5 For example, M= )AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAA5 comparisons made Total number of comparisons: M Best case time complexity: (M)7 STRINGS and PATTERN MatchingBrute Force-Complexity(cont.) Given a PATTERN M characters in length, and a text Ncharacters in Best case if PATTERN not found: Always mismatchon first character. For example, M= )AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made2) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made3) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made4) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made5) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison ) AAAAAAAAAAAAAAAAAAAAAAAAAAAH1 comparison madeOOOOH Total number of comparisons: N Best case time complexity.

6 (N)8 STRINGS and PATTERN MatchingRabin-Karp The Rabin-Karp string searching algorithm uses ahash function to speed up the & Karp sFresh from SyriaHeavenlyHomemade Hashish9 STRINGS and PATTERN MatchingRabin-Karp The Rabin-Karp string searching algorithmcalculates ahash valuefor the PATTERN , and for eachM-character subsequence of text to be compared. If the hash values are unequal, the algorithm willcalculate the hash value for next M-charactersequence. If the hash values are equal, the algorithm will do aBrute Force comparisonbetween the PATTERN and theM-character sequence.

7 In this way, there is only one comparison per textsubsequence, and Brute Force is only needed whenhash values match. Perhaps a figure will clarify some and PATTERN MatchingRabin-Karp ExampleHash value of AAAAA is 37 Hash value of AAAAH is 1001)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison made2) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison made3) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison made4) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison ) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH6 comparisons made 100=10011 STRINGS and PATTERN MatchingRabin-Karp Pseudo-Codepattern is M characters longhash_p=hash value of patternhash_t=hash value of first M letters inbody of textdoif (hash_p ==hash_t)brute force comparison of patternand selected section of texthash_t = hash value of next section of text, one character overwhile (end of textor brute force comparison == true)12 STRINGS and PATTERN MatchingRabin-Karp Common Rabin-Karp questions.

8 What is the hash function used to calculatevalues for character sequences? Isn t it time consuming to hashevery one of the M-charactersequences in the text body? Is this going to be on the final? To answer some of these questions, we ll have to and PATTERN MatchingRabin-Karp Math Consider an M-character sequence as an M-digitnumber inbaseb, wherebis the number of letters inthe alphabet . The text subsequence t[i .. i+M-1] ismapped to the numberx(i) =t[i] bM-1 +t[i+1] bM-2 +..+t[i+M-1] Furthermore, given x(i) we can compute x(i+1) forthe next subsequence t[i+1.]

9 I+M] in constant time,as follows:x(i+1) =t[i+1] bM-1 +t[i+2] bM-2 +..+t[i+M]x(i+1) =x(i) bShift left one digit-t[i] bM Subtract leftmost digit+t[i+M] Add new rightmost digit In this way, we never explicitly compute a newvalue. We simply adjust the existing value as wemove over one and PATTERN MatchingRabin-Karp Mods If M is large, then the resulting value (~bM) will beenormous. For this reason, we hash the value bytaking itmod a prime numberq. Themod function (% in Java) is particularly usefulin this case due to several of its inherent properties:- [(x mod q) + (y mod q)] mod q = (x+y) mod q- (x mod q) mod q = x mod q For these reasons:h(i) = ((t[i] bM-1 modq) +(t[i+1] bM-2 modq) +.)

10 +(t[i+M-1] modq)) modqh(i+1) =(h(i) b modqShift left one digit-t[i] bM modqSubtract leftmost digit+t[i+M] modq )Add new rightmost digitmodq15 STRINGS and PATTERN MatchingRabin-Karp Pseudo-Codepattern is M characters longhash_p=hash value of patternhash_t=hash value of first M letters in body of textdoif (hash_p==hash_t)brute force comparison of patternand selected section of texthash_t = hash value of next section of text, one character overwhile (end of textor brute force comparison ==true)16 STRINGS and PATTERN MatchingRabin-Karp Complexity If a sufficiently large prime number is used for thehash function, the hashed values of two differentpatterns will usually be distinct.