Scribd
Upload
2 views36 pages

M3 String Matching Algorithms

The document discusses various applications of string searching algorithms, including spell checkers, spam filters, intrusion detection systems, and bioinformatics. It details the classification of string matching algorithms, focusing on the naive method and the Knuth-Morris-Pratt algorithm, which involves creating a one-dimensional array to optimize pattern searching. The document outlines the steps for implementing the Knuth-Morris-Pratt algorithm to efficiently find patterns in text.

Uploaded by

chaaait
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views36 pages

M3 String Matching Algorithms

The document discusses various applications of string searching algorithms, including spell checkers, spam filters, intrusion detection systems, and bioinformatics. It details the classification of string matching algorithms, focusing on the naive method and the Knuth-Morris-Pratt algorithm, which involves creating a one-dimensional array to optimize pattern searching. The document outlines the steps for implementing the Knuth-Morris-Pratt algorithm to efficiently find patterns in text.

Uploaded by

chaaait
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

String Searching Algorithms

• Spell Checkers
• Spam Filters
• Intrusion Detection System
• Search Engines Plagiarism Detection
Bioinformatics,
• Digital Forensics and Information
Retrieval Systems and etc.
Spell Checkers
Spam Filters / Spam Detection
Systems
Intrusion Detection System
Plagiarism Detection
Search Engines / Content Searching in
Large Databases
Bioinformatics / DNA Sequencing
Digital Forensics
Information Retrieval
Classification of String Matching Algorithms
Single – Pattern Matching
Few variables

n: the length of the text


m: the length of the pattern(string)
Cn: the expected number of comparisons
performed by an algorithm while searching
the pattern in a text of length n
Naive Method – Brute - Force
Knuth-Morris-Pratt Algorithm
Step 1: Create a one-dimensional array with a size equal to the Pattern's
length. (LPS[size])

Step 2: Create variables i and j. Set i = 0, j = 1, and LPS[0] = 0 for i j, and


LPS[0] respectively.

Step 3: Compare the Pattern[i] and Pattern[j] characters.

Step 4 - If both are equal, set LPS[j] = i+1 and add one to both i and j values.
Step 3 is the next step.

Step 5 - Check the value of variable i if both aren't matched. If it's '0,' set
LPS[j] = 0 and increase the value of 'j' by one; if it's not, set i = LPS[i-1]. Goto
Step three.

Step 6- Repeat steps 1-5 until all of the LPS[] values are filled.
More Example
More Example

You might also like