STRINGS AND PATTERN MATCHING - Purdue University

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

Rabin-Karp Complexity • If a sufficiently large prime number is used for the hash function, the hashed values of two different patterns will usually be distinct. • If this is the case, searching takes O(N) time, where N is the number of characters in the larger body of text.

Loading..

Tags:

  Brain

Information

Related search queries