3.2- Sequential Search & Brute-Force String Matching

Question 1

A simple extra trick is often employed
in implementing sequential search:

Answer 1

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.

Question 2

improvement can be incorporated in sequential
search if

Answer 2

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.

Question 3

Sequential search provides an excellent illustration of the brute-force approach,

Answer 3

with its characteristic strength (simplicity) and weakness (inferior efficiency).

Question 4

given a string of n
characters called the_____ and a string of m characters (m ≤ n) called the______,
find a substring of the text that matches the pattern. To put it more precisely, we
want to find i—the index of the leftmost character of the first matching substring

Answer 4

text
pattern

Question 5

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 m pairs
of the characters match (then the algorithm can stop) or a mismatching pair is
encountered.

Answer 5

In the latter case, shift the pattern one position to the right and
resume the character comparisons, starting again with the first character of the
pattern and its counterpart in the text. Note that the last position in the text that
can still be a beginning of a matching substring is n − m(provided the text positions
are indexed from 0 to n − 1). Beyond that position, there are not enough characters
to match the entire pattern; hence, the algorithm need not make any comparisons
there.