Data Structure and Algorithms
Siper
DSAlg-StringMatching.pptxMCIS 6214 - Data Structure and Algorithms Space and Time Trade-Offs
MCIS 2018
1
Brute Force
Sorting by Counting
Overview
2
2
Brute Force
3
Brute Force - A straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.
Introduction to The Design and Analysis of Algorithms 3rd edition
3
Selection Sort
4
Scanning the entire given list to find its smallest element
and exchange it with the first element, putting the
smallest element in its final position in the sorted list.
Introduction to The Design and Analysis of Algorithms 3rd edition
4
Selection Sort
5
Example of selection sort
Introduction to The Design and Analysis of Algorithms 3rd edition
5
Selection Sort
6
Analysis
Introduction to The Design and Analysis of Algorithms 3rd edition
6
Sorting by Counting
7
7
Sorting by Counting
8
8
Sorting by Counting
9
This algorithm makes the minimum number of key moves, possible, placing each of them directly in their final position in a sorted array.
Introduction to The Design and Analysis of Algorithms 3rd edition
9
Brute-Force String Matching
10
Given a string of n characters called the Text
A string of m characters ( m <= n ) called a pattern
Find a substring of the Text that matches the pattern
(Find location I – the index of the left most character
of the first matching substring )
Introduction to The Design and Analysis of Algorithms 3rd edition
10
Brute-force String Matching
11
Algorithm
Introduction to The Design and Analysis of Algorithms 3rd edition
11
Brute-force String Matching – Example
12
Introduction to The Design and Analysis of Algorithms 3rd edition
12
Horspool’s Algorithm
13
Consider, as an example, searching for the pattern BARBER in some text:
Starting with the last R of the pattern and moving right to left, we compare the corresponding pairs of characters in the pattern and the text.
If all the pattern’s characters match successfully, a matching substring is found.
Then the search can be either stopped altogether or continued if another occurrence of the same pattern is desired.
Introduction to The Design and Analysis of Algorithms 3rd edition
13
Horspool’s Algorithm
14
Consider, as an example, searching for the pattern BARBER in some text:
Starting with the last R of the pattern and moving right to left, we compare the corresponding pairs of characters in the pattern and the text.
If all the pattern’s characters match successfully, a matching substring is found.
Then the search can be either stopped altogether or continued if another occurrence of the same pattern is desired.
Introduction to The Design and Analysis of Algorithms 3rd edition
14
Horspool’s Algorithm – Case 1
15
If there are no c’s in the pattern—e.g., c is letter S in our example— we can safely shift the pattern by its entire length (if we shift less, some character of the pattern would be aligned against the text’s character c that is known not to be in the pattern):
Introduction to The Design and Analysis of Algorithms 3rd edition
15
Horspool’s Algorithm – Case 2
16
If there are occurrences of character c in the pattern but it is not the last one there—e.g., c is letter B in our example—the shift should align the rightmost occurrence of c in the pattern with the c in the text:
Introduction to The Design and Analysis of Algorithms 3rd edition
16
Horspool’s Algorithm – Case 3
17
If c happens to be the last character in the pattern but there are no c’s among its other m − 1 characters—e.g., c is letter R in our example—the situation is similar to that of Case 1 and the pattern should be shifted by the entire pattern’s length m:
Introduction to The Design and Analysis of Algorithms 3rd edition
17
Horspool’s Algorithm – Case 4
18
Finally, if c happens to be the last character in the pattern and there are other c’s among its first m − 1 characters—e.g., c is letter R in our example— the situation is similar to that of Case 2 and the rightmost occurrence of c among the first m − 1 characters in the pattern should be aligned with the text’s c:
Introduction to The Design and Analysis of Algorithms 3rd edition
18
Horspool’s Algorithm – Precompute shift size
19
The table will be indexed by all possible characters that can be encountered in a text, including, for natural language texts, the space, punctuation symbols, and
other special characters.
Introduction to The Design and Analysis of Algorithms 3rd edition
19
Horspool’s Algorithm – HorspoolMatching
20
Introduction to The Design and Analysis of Algorithms 3rd edition
20
Horspool’s Algorithm – Example
21
Find the pattern “BARBER”
form the Given String
“J I M _ S A W _ M E _ I N _ A _ B A R B E R S H O P”
Introduction to The Design and Analysis of Algorithms 3rd edition
21
Horspool’s Algorithm – Example
22
Introduction to The Design and Analysis of Algorithms 3rd edition
22
Horspool’s Algorithm – Exercise
23
Introduction to The Design and Analysis of Algorithms 3rd edition
TCCTATTCTT
TTATAGATCTCGTATTCTTCCTATTCTTTTTATAGATC
23
