The first deals with the canonical problem of searching for an item of a given value in a given list. The second is different in that it deals with the string-matching problem.

**Sequential
Search and Brute-Force String Matching**

We saw in
the previous section two applications of the brute-force approach to the sorting
porblem. Here we discuss two applications of this strategy to the problem of
searching. The first deals with the canonical problem of searching for an item
of a given value in a given list. The second is different in that it deals with
the string-matching problem.

We have
already encountered a brute-force algorithm for the general searching problem:
it is called sequential search (see Section 2.1). To repeat, the algorithm
simply compares successive elements of a given list with a given search key
until either a match is encountered (successful search) or the list is
exhausted without finding a match (unsuccessful search). A simple extra trick
is often employed in implementing sequential search: if we append the search
key to the end of the list, the search for the key will have to be successful,
and therefore we can eliminate the end of list check altogether. Here is
pseudocode of this enhanced version.

**ALGORITHM** *SequentialSearch2*** (A**[0

//Implements
sequential search with a search key as a sentinel //Input: An array ** A** of

//Output:
The index of the first element in ** A**[0..

equal to ** K** or −1 if no such element is found

** A**[

**while **** A**[

**if ***i < n*** return ***i*** else return **−1

Another
straightforward improvement can be incorporated in sequential search if a given
list is known to be sorted: searching in such a list can be stopped as soon as
an element greater than or equal to the search key is encountered.

Sequential
search provides an excellent illustration of the brute-force ap-proach, with
its characteristic strength (simplicity) and weakness (inferior effi-ciency).
The efficiency results obtained in Section 2.1 for the standard version of
sequential search change for the enhanced version only very slightly, so that
the algorithm remains linear in both the worst and average cases. We discuss
later in the book several searching algorithms with a better time efficiency.

** **Sequential
Search and Brute-Force String Matching

**Brute-Force
String Matching**

Recall
the string-matching problem introduced in Section 1.3: given a string of ** n** characters called the

If
matches other than the first one need to be found, a string-matching algorithm
can simply continue working until the entire text is exhausted.

A
brute-force algorithm for the string-matching problem is quite obvious: align
the pattern against the first ** m**
characters of the text and start matching the corresponding pairs of characters
from left to right until either all the

**ALGORITHM** *BruteForceStringMatch**(T** *[0*..n** *−* *1]*, P** *[0*..m** *−* *1]*)*

//Implements
brute-force string matching

//Input:
An array ** T** [0

an array ** P** [0

matching substring or −1 if the search is unsuccessful

**for ***i*** **←** **0** to ***n*** **−** ***m*** do **** j **←

**while ***j
< m*** and ***P*** **[*j*** **]** **=** ***T*** **[*i*** **+** ***j*** **]** do **** j **←

**if ***j*** **=** ***m*** return ***i*** return **−1

An
operation of the algorithm is illustrated in Figure 3.3. Note that for this
example, the algorithm shifts the pattern almost always after a single
character comparison. The worst case is much worse: the algorithm may have to
make all ** m** comparisons before shifting the
pattern, and this can happen for each of the

**FIGURE 3.3
**Example of brute-force string matching. The
pattern’s characters that are** **compared
with their text counterparts are in bold type.

** m(n **−

**Exercises
3.2**

Find the
number of comparisons made by the sentinel version of sequential search in the
worst case.

** **in the
average case if the probability of a successful search is ** p (**0 ≤

As shown
in Section 2.1, the average number of key comparisons made by sequential search
(without a sentinel, under standard assumptions about its inputs) is given by
the formula

where ** p** is the probability of a
successful search. Determine, for a fixed

*Gadget testing *A firm wants to determine the
highest floor of its* *** n**-story

**
**Determine the number of character comparisons made
by the brute-force algorithm in searching for the pattern GANDHI in the
text

THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED

Assume
that the length of the text—it is 47 characters long—is known before the search
starts.

**
**How many comparisons (both successful and
unsuccessful) will be made by the brute-force algorithm in searching for each
of the following patterns in the binary text of one thousand zeros?

**a. **00001 **b. **10000 **c. **01010

**
**Give an example of a text of length ** n** and a pattern of length

**
**In solving the string-matching problem, would there
be any advantage in comparing pattern and text characters right-to-left instead
of left-to-right?

**
**Consider the problem of counting, in a given text,
the number of substrings that start with an A and end with a B. For example, there are four such substrings in CABAAXBYA.

**
**Design a brute-force algorithm for this problem and
determine its effi-ciency class.

**
**Design a more efficient algorithm for this problem.
[Gin04]

**
**Write a visualization program for the brute-force
string-matching algorithm.

**
***Word Find
*A popular
diversion in the United States, “word find” (or “word* *search”) puzzles ask the player to find each of a given set of
words in a square table filled with single letters. A word can read
horizontally (left or right), vertically (up or down), or along a 45 degree
diagonal (in any of the four directions) formed by consecutively adjacent cells
of the table; it may wrap around the table’s boundaries, but it must read in
the same direction with no zigzagging. The same cell of the table may be used
in different words, but, in a given word, the same cell may be used no more
than once. Write a computer program for solving this puzzle.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Brute Force and Exhaustive Search : Sequential Search and Brute-Force String Matching |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.