Chapter 32, Problem 1P

a.

Program Plan Intro

To give and efficient algorithm that takes pattern P [1 . . m ] as input and computes the values of $\rho \left(P_i\right)$ for $i=1,2,\dots m$

Explanation of Solution

String matching based on repetition factors:

String matching is the method of finding some particular pattern in the whole string. There are two things one is pattern and one is whole string. The string matching refers to just check whether the given pattern is present in the string or not also to find out the position of the first letter of the patter till the length of the pattern. It may be in form of sequence or tree structures.

Suppose the input is a pattern $P\left[\mathrm{1..}m\right]$ and the following algorithm calculates the value $\rho \left(P_i\right)$

The first approach is the Naïve Approach.

The algorithm is given below:

  $1i=$ Text size 0

  $//$ inputs text size

  $2m=$ Pattern size 0

  $//$ inputs the text pattern

3 for $a=0$ to $n-m$ \{4

  $5$ if ( pattern $[1\dots .\text{m}]=\mathrm{text}[\text{a}+1\dots \text{a}+\text{m}])$

add-result $(a)$

6\}

The running of the algorithm would be $\Theta \left(m^2\right)$ .This is because one power of m for loop that is “for” loop (worst case) and another for checking process of “if” statement because it is run up-to m in worst case scenario.

b.

Program Plan Intro

To prove that the expected value of ${\rho }^{*}\left(P\right)$ is $O\left(1\right)$ if the pattern P is chosen randomly form the set of all binary strings of length m .

Explanation of Solution

Taking the pattern $P\left[\mathrm{1..}m\right]$ and is defined as ${\rho }^{*}\left(P\right)$ is defined as ${\max }_{1\le i\le m}\rho \left(P_i\right)$

Taking the pattern involving one string: xor y

When matching the above pattern, it iterates in one cycle maximum.

Taking the pattern involving two strings:

or

or

When trying to match the given string with the above pattern. It will match the string as single one or the text as a two together completing it in maximum one or two iteration.

Taking the pattern of three strings:

Again, while trying to match the above string either it matches a single string or a few strings together or all might be same.

Similarly, it can be done so for mstrings . Each time involving $O\left(1\right)$ time maximum

c.

Program Plan Intro

To argue that the string matching algorithm correctly find all occurrences of the patternP in a text $T\left[\mathrm{1....}n\right]$ taking the time $O\left({\rho }^{*}\left(P\right)n+m\right)$ .

Explanation of Solution

The given Galil-Seiferas algorithm consists of preprocessing phase and searching phase.The preprocessing phase of Galil-Seiferas algorithm involves finding decompositionab of x followingb that has at least one prefix period and $\left|a\right|=O\left(per\left(b\right)\right)$ the searching phase works in scanning the text for each occurrence of bandb checks immediately if aoccurs just beforeb .

  

While searching for $x\left[s\mathrm{...}m-1\right]$ in y :

1. If $x\left[s\mathrm{....}s+p_1+q_1-1\right]$ matches with a shift of length $p_1$ , the comparisons are continued with $x\left[s+q_1\right]$ .
2. Each time the mismatch occurs with $x\left[s+q\right]$ and $q=p_1+q_1$ then a shift of length $q/d+1$ can be done and comparisons are carried with $x\left[0\right]$ .

The preprocessing will incur $O\left(m\right)$ times and the searching phase $O\left(n\right)$ times and it is noticed in line 3 of algorithm that algorithm runs for ${\rho }^{*}\left(P\right)$ . The total process therefore will take $O\left({\rho }^{*}\left(P\right)n+m\right)$ time.