Question

In this exercise we deal with the problem of string matching.

1. Explain how to use a brute-force algorithm to find the first occurrence of a given of m characters, called the target, in a string of n characters, where$\mathit{m}\mathbf{\le }\mathit{n}$, called the text. [Hint: Think in terms of finding a match for the first character of the target and checking successive characters for a match, and if they do not all match, moving the start location one character to the right].
2. Express your algorithm in pseudocode.
3. Give a big-O estimate for the worst-case time complexity of the brute-force algorithm you described.

Short answer

1. If match is found, algorithm should stop and return to the location of the occurrence of string.
2. else i := i + 1

return location.

3. O(n log n)

Step-by-step solution

(a)Step 1: Brute-force algorithm

We have two strings: one string $a_1{a}_2...a_n$with n characters and one string data-custom-editor="chemistry" $b_1,b_2...{\mathrm{b}}_{\mathrm{m}}$ with m characters with .

We want to determine if the string occurs within the string $m\le n$.

We will first check if the first element $b_1$is in the string role="math" localid="1668668563903" $b_1{b}_2...b_m$ (thus need to check it for $a_{1}to{a}_{n-m+1}$, because if is one of the other elements, then the entire string role="math" localid="1668668556255" $b_1{b}_2...{\mathrm{b}}_m$cannot be within $a_1{a}_2...a_n$).

If the element is found, then the algorithm needs to check if the next character in $a_1{a}_2...a_n$is $b_1$. If it is, then we need to check if the next character $b_3$and so on.

If they do not match, then we need to move the start location to the next character.

If a match is found, the algorithm should stop and return the location of the occurrence of the string $b_1{b}_2...b_m$in $a_1{a}_2...a_n$.

Note: If the algorithm returns the empty set $\varphi$, then this will mean that the string $b_1{b}_2...b_m$does not occur in $a_1{a}_2...a_n$.

(b) Step 2: Write algorithm

We call the algorithm “string matching” and the input is two strings: one stringwith n characters and one string$b_1{b}_2...b_m$with m characters with$m\le n$.

Procedure: string matching$(a_1{a}_2...a_n:stringwithn\ge 1,b_1{b}_2...b_{m}stringwith1\le m\le n)$.

The variable “location” will keep track if a location of the string is found. The value $\varphi$indicates that no match is found. The variable i will keep track of position in the string $a_1{a}_2...a_n$where we are currently checking for $b_1$.

location :=$\varphi$

i := 1

If a match is found, the algorithm should stop and return the location of the occurrence of the string$b_1{b}_2...b_m$in$a_1{a}_2...a_n$.

We will first check if the first element$b_1{b}_2...b_m$is in the stringdata-custom-editor="chemistry" $a_1{a}_2...a_n$.

If the element$b_1$is found, then the algorithm needs to check if the next character in$a_1{a}_2...a_n$is$b_2$. If it is, then we need to check if the next character is$b_3$and so on.

If they do not match, then we need to move the start location to the next character.

The variable j will keep track of the location in the string$b_1{b}_2...b_m$. If no match is found, we set the value of j to$m+2$such that the while-loop will stop and such that j reaching the value m + 1 means that every character in the string $b_1{b}_2...b_m$was matched.

while$i\le n-m+1andlocation=\varphi$

if$b_1=a_i$then

$j:=2$

while$j\le mandlocation=\varphi$

ifrole="math" localid="1668669455924" $b_j\ne a_{\mathit{i}\mathbf{+}\mathit{j}\mathbf{-}\mathbf{1}}$then

$$\begin{gathered} i:=i+j \\ j:=m+2 \end{gathered}$$

else $j:=j+1$

if$j=m+1thenlocation:=\left\{i,i+1,i+2,...i+m-1\right\}$

else role="math" localid="1668669561235" $i:=i+1$

(c)Step 3: Write algorithm

Finally, the algorithm should return the variable “location” which keep track of the location of$b_1{b}_2...b_m$in the string$a_1{a}_2...a_n$.

return location.

Combining all these steps, we then obtain the algorithm:

Procedure- string matching$(a_1{a}_2...a_n:stringwithn\ge 1,b_1{b}_2...b_{m}stringwith1\le m\le n)$

$$\begin{gathered} location:=\varphi \\ i:=1 \end{gathered}$$

while$i\le n-m+1andlocation=\varphi$

if$b_1=a_i$then

$j:=2$

while$j\le mandlocation=\varphi$

if$b_j\ne a_{i+j-1}$then

$$\begin{gathered} i:=i+j \\ j:=m+2 \end{gathered}$$

else $j:=j+1$

if $j=m+1$then$location:=\left\{i,i+1,i+2,...,i+m-1\right\}$

else $i:=i+1$

return location.

(d) Step 4: Worst case scenario

If the entire string $a_1{a}_2...a_n$does not contains $b_1$, then the outer while-loop is executed n - m + 1 times and the inner while-loop is never executed. The outer while-loop makes 3 comparisons per iteration comparisons made.

Worst-case scenario- If the string role="math" localid="1668670033252" $a_1{a}_2...a_n$is made up out of the substrings $b_1{b}_2...b_{m-1}$then the inner while-loop is executed times before ending and the inner while-loop is executed $\lfloor lo{g}_{m-1}n\rfloor$times before ending. The outer while-loop made comparisons, while the inner while-loop made 3 comparisons.

In total, the algorithm, then makes data-custom-editor="chemistry" $4(m-2)\cdot (4+3)\lfloor lo{g}_{m-1}n\rfloor =28(n-2)\lfloor lo{g}_{m-1}n\rfloor$comparisons and $23(m-2)\lfloor lo{g}_{m-1}n\rfloor isO(nlogn)(sincem\le n)$.