Scribd
Upload
67 views8 pages

Exact String Matching Algorithms Overview

This document summarizes several string matching algorithms, including the brute force algorithm, Karp-Rabin algorithm, Knuth-Morris-Pratt algorithm, Shift-Or algorithm, and Boyer-Moore algorithm. It introduces string searching as finding patterns within strings by outputting all occurrences of a pattern in text, where the pattern is a substring of length m and the text is a string of length n. It also describes the basic sliding window mechanism used by these algorithms to scan the text with a window of size m and shift it right after each attempt or mismatch.

Uploaded by

Himanshu Patidar
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
67 views8 pages

Exact String Matching Algorithms Overview

This document summarizes several string matching algorithms, including the brute force algorithm, Karp-Rabin algorithm, Knuth-Morris-Pratt algorithm, Shift-Or algorithm, and Boyer-Moore algorithm. It introduces string searching as finding patterns within strings by outputting all occurrences of a pattern in text, where the pattern is a substring of length m and the text is a string of length n. It also describes the basic sliding window mechanism used by these algorithms to scan the text with a window of size m and shift it right after each attempt or mismatch.

Uploaded by

Himanshu Patidar
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Exact string

matching
Algorithms

Himanshu Patidar
Manish Chouriya
Shubham Patidar
 Introduction
 Brute Force Algorithm
 Karp-Rabin Algorithm
 Knuth-Morris-Pratt Algorithm
 Shift-Or Algorithm
 Boyer-Moore Algorithm
 Bibliography
Introduction
 String searching algorithms search for patterns
within strings.

 They outputs all occurrences of a pattern in a text.

 Pattern: x = x[0. .m-1] (length = m)


Text string: y=y[0. .n-1] (length = m)
Working:
 Scan text with help of a window (size = m).
 Firstly, left ends of window and text are left-
aligned and then compared- ‘Attempt’.
 After, a whole pattern match or mismatch – shift
the window to right.
 Repeatthe procedure – until right end of window
goes beyond right end of text.

 Mechanism is known as sliding window


mechanism.

You might also like