Unit- V

String-Matching Algorithms: Naïve string Matching; Rabin - Karp

algorithm; String matching with finite automata; Knuth-Morris-Pratt
algorithm; Boyer– Moore Algorithm.
Probabilistic algorithms; Randomizing Deterministic Algorithms

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 1

 Naïve string Matching
• Text is an array T [1 n] of length n and that the pattern is an array P[1 m]
of length m ≤ n. The elements of P and T are characters drawn from a
finite alphabet Σ. For example, we may have Σ = {0, 1} or Σ = {a, b, . . . , z}.
The character arrays P and T are often called strings of characters.
• We say that pattern P occurs with shift s in text T if 0 ≤ s ≤ n - m and
T [s + 1….. s + m] = P[1…m] (that is, if T [s + j] = P[ j], for 1 ≤ j ≤ m).
• If P occurs with shift s in T , then we call s a valid shift; otherwise, we call s
an invalid shift.
• The string-matching problem is the problem of finding all valid shifts with
which a given pattern P occurs in a given text T.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 2

The naive algorithm
• The naive algorithm finds all valid shifts using a loop that checks the
condition P[1… m] = T [s + 1… s + m] for each of the n - m + 1 possible
values of s.
• NAIVE-STRING-MATCHER(T, P)
1. n ← length[T]
2. m ← length[P]
3. for s ← 0 to n - m
4. do if P[1… m] = T[s + 1… s + m]
5. then print "Pattern occurs with shift" s

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 3

• The naive string-matching procedure can be interpreted graphically as sliding a
"template" containing the pattern over the text, noting for which shifts all of the
characters on the template equal the corresponding characters in the text
• The for loop beginning on line 3 considers each possible shift explicitly.
• The test on line 4 determines whether the current shift is valid or not; this test
involves an implicit loop to check corresponding character positions until all
positions match successfully or a mismatch is found. Line 5 prints out each valid
shift s.
• The worst case time complexity is O((n-m+1)m)=O(nm) because nm≥m2 for n≥m
• Example : Text : acaabc, Pattern : aab

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 4

Rabin-Karp string matching algorithm
• Uses concept of hashing
• Works on numerical data
• Example: Text: abcababcd Pattern: aba

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 5

Consider another example
Text: abbcaaca Pattern: aca

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 6

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 7
Rabin-Karp string matching algorithm
• let us assume that Σ = {0, 1, 2, . . . , 9}, so that each character is a
decimal digit. In the general case, we can assume that each character
is a digit in radix-d notation, where d = |Σ|.
• We can then view a string of k consecutive characters as representing
a length-k decimal number. That is the character string 31415 thus
corresponds to the decimal number 31,415.
• Given a pattern P[1…m], we let p denote its corresponding decimal
value.
• In a similar manner, given a text T [1…n], we let ts denote the
decimal value of the length-m substring T[s + 1… s + m], for s = 0, 1, . .
. , n - m.
• Certainly, ts = p if and only if T [s + 1…s + m] = P[1…m]; thus, s is a
valid shift if and only if ts = p.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 8

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 9
• To compute the remaining values t1, t2, . . . , t n-m in time Θ(n - m), it
suffices to observe that ts+1 can be computed from ts in constant
time,

Subtracting 10m-1 T[s + 1] removes the high-order digit from ts,

multiplying the result by 10 shifts the number left one position, and
adding T [s + m + 1] brings in the appropriate loworder digit.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 10

• The only difficulty with this procedure is that p and ts may be too
large to work with conveniently. If P contains m characters, then
assuming that each arithmetic operation on p (which is m digits long)
takes "constant time" is unreasonable. Fortunately, there is a simple
cure for this problem,
• we choose q so that dq fits within a computer word and adjust to
work modulo q, so that it becomes

• where h = dm-1 (mod q) is the value of the digit "1" in the high-order
position of an m-digit text window.
20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 11
Example: P[1…m]= “31415”, Let q=13 Then p=31415 mod 13=7
T[1…n]=“ 2359023141526739921”

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 12

• In the figure
• (a) A text string. A window of length 5 is shown shaded. The numerical
value of the shaded number is computed modulo 13, yielding the value 7.
• (b) The same text string with values computed modulo 13 for each
possible position of a length-5 window. Assuming the pattern P = 31415,
we look for windows whose value modulo 13 is 7, since 31415 ≡ 7 (mod
13). Two such windows are found, shown shaded in the figure. The first,
beginning at text position 7, is indeed an occurrence of the pattern, while
the second, beginning at text position 13, is a spurious hit.
• (c) Computing the value for a window in constant time, given the value for
the previous window. The first window has value 31415. Dropping the high-
order digit 3, shifting left (multiplying by 10), and then adding in the low
order digit 2 gives us the new value 14152. All computations are performed
modulo 13, however, so the value for the first window is 7, and the value
computed for the new window is 8.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 13

• The inputs to the procedure are the text T , the pattern P, the radix d to use
(which is typically taken to be |Σ|), and the prime q to use.
• RABIN-KARP-MATCHER(T, P, d, q)
1 n ← length[T]
2m ← length[P]
3 h ← dm-1 mod q
4p←0
5 t0 ← 0
6 for i ← 1 to m // Preprocessing.
7 do p ← (dp + P[i]) mod q
8 t0 ← (dt0 + T[i]) mod q
9 for s ← 0 to n - m // Matching.
10 do if p = ts
11 then if P[1… m] = T [s + 1…s + m]
12 then print "Pattern occurs with shift" s
13 if s < n - m
14 then ts+1 ← (d(ts - T[s + 1]h) + T[s + m + 1]) mod q
20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 14
• RABIN-KARP-MATCHER takes Θ(m) preprocessing time, and its
matching time is Θ((n - m + 1)m) in the worst case, since (like the
naive string-matching algorithm) the Rabin-Karp algorithm explicitly
verifies every valid shift. If P = am and T = an , then the verifications
take time Θ((n - m + 1)m), since each of the n - m + 1 possible shifts is
valid.
• Applications: Used in bioinformatics- Used in looking for similarities of
2 or more proteins, ie, high sequence similarity usually implies
significant structural or functional similarity

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 15

String matching with finite automata
• The string-matching automata are very efficient: they examine each text
character exactly once, taking constant time per text character.
• The matching time used-after preprocessing the pattern to build the
automaton-is therefore Θ(n).
•A finite automaton M is a 5-tuple (Q, q0, A, Σ, δ), where
Q is a finite set of states,
q0 € Q is the start state,
A is subset of Q is a distinguished set of accepting states,
Σ is a finite input alphabet,
δ is a function from Q × Σ into Q, called the transition function of M.
The finite automaton begins in state q0 and reads the characters of its input
string one at a time. If the automaton is in state q and reads input character
a, it moves ("makes a transition") from state q to state δ(q, a). Whenever its
current state q is a member of A, the machine M is said to have accepted the
string read so far.
20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 16
• Figure illustrates these definitions with a simple two-state automaton.

Fig shows simple two-state finite automaton with state set Q = {0, 1},
start state q0 = 0, and input alphabet Σ = {a, b}.
Fig (a) A tabular representation of the transition function δ.
Fig (b) An equivalent state-transition diagram. State 1 is the only
accepting state (shown blackened). Directed edges represent
transitions. For example, the edge from state 1 to state 0 labeled b
indicates δ(1, b) = 0. This automaton accepts those strings that end in
an odd number of a's.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 17

String-matching automata
• In a string-matching automaton for every pattern P; this automaton
must be constructed from the pattern in a preprocessing step before
it can be used to search the text string.
• In order to specify the string-matching automaton corresponding to a
given pattern P[1…m], we first define an auxiliary function σ , called
the suffix function corresponding to P.
• The function σ is a mapping from Σ* to {0, 1, . . . , m} such that σ(x) is
the length of the longest prefix of P that is a suffix of x:

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 18

• We define the string-matching automaton that corresponds to a given
pattern P[1…m] as follows.
• The state set Q is {0, 1, . . . , m}. The start state q0 is state 0, and state
m is the only accepting state.
• The transition function δ is defined by the following equation, for any
state q and character a:

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 19

Example: Text: abababacaba
Pattern: ababaca
• Initially rough state-transition diagram for the string-matching
automaton that accepts all strings ending in the string ababaca and it’s
transition table is shown below. State 0 is the start state, and state 7 is
the only accepting state. A directed edge from state i to state j labeled a
represents δ(i, a) = j.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 20

 Pattern: ababaca
Then construct transition table using

Corresponding final transition diagram for the pattern is as shown below

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 21

• We can find all occurrence of pattern of length m on text of length n
by checking whether can we reach to final state from initial state.
• For the example discussed one occurrence of pattern found ending in
position 9 shown in figure below.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 22

Algorithms used
• FINITE-AUTOMATON-MATCHER(T, δ, m)
1 n ← length[T]
2q←0
3 for i ← 1 to n
4 do q ← δ(q, T[i])
5 if q = m
6 then print "Pattern occurs with shift" i – m
COMPUTE-TRANSITION-FUNCTION(P, Σ)
1 m ← length[P]
2 for q ← 0 to m
3 do for each character a € Σ
4 do k ← min(m + 1, q + 2)
5 repeat k ← k – 1
6 until Pk Pqa
7 δ(q, a) ← k
80-1r2e-2t0u23rn δ
2 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 23
Boyer-Moore Algorithm
• Boyer-Moore algorithm starts by aligning the pattern against the
beginning characters of the text; Then comparisons start with the last
character in the pattern with aligned text. This idea leads to simpler
algorithm
The simplified version of the Boyer-Moore algorithm is Horspool’s algorithm.
To have maximum shift of pattern over the text when mismatch of character
between text and pattern occurs on comparison, Boyer-Moore algorithm has
2 preprocessing steps
1. Constructing bad –symbol shift table
2. Constructing good suffix shift table

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 34

Constructing bad –symbol shift table
• Consider searching for the pattern BARBER in some text:

• There are 4 cases to be considered for constructing bad-symbol shift

table.
• Case 1: If the text character c which is in line with right most
character of pattern is not matching and that text character c is not
there in the pattern —e.g., letter S in our example— we can safely
shift the pattern by its entire length

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 35

• Case 2: If the text character c which is in line with right most
character of pattern is not matching but there are occurrences of that
text character c in the pattern, then shift should align the rightmost
occurrence of that text character c in the pattern with the c in the
text

• Case 3: If text character c happens to be the last character in the

pattern but there are no c’s among its other m − 1 ,then pattern
should be shifted by the entire pattern’s length m

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 36

• Case 4: Finally, if text character c happens to be the last character in
the pattern and there are other c’s among its first m − 1 charecters in
pattern then rightmost occurrence of c among the first m − 1
characters in the pattern should be aligned with the text’s c

• To search for the pattern BARBER in a text that comprises English

letters and spaces (denoted by underscores). The bad –symbol shift
table is :

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 37

• If the first comparison of the rightmost character in the pattern with
the corresponding character c in the text fails, the algorithm does
exactly the same thing as Horspool’s algorithm.
• In above cases few characters matched is not taken into consideration
• However, after some positive number k (0 < k < m) of the pattern’s
characters are matched successfully before a mismatch is
encountered with text character c as shown below

Then the size of this shift can be computed by the formula t1(c) − k
where t1(c) is the entry in the precomputed table used by Horspool’s
algorithm and k is the number of matched characters

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 38

• For example, if we search for the pattern BARBER in some text and match the last
two characters before failing on letter S in the text, we can shift the pattern by
t1(S) − 2 = 6 − 2 = 4 positions:

Here if we have used Horspool’s method shift would have been 3 positions which is
not good choice.
The same formula can also be used when the mismatching character c of the text
occurs in the pattern, provided t1(c) − k > 0. For example, if we search for the
pattern BARBER in some text and match the last two characters before failing on
letter A, we can shift the pattern by t1(A) − 2 = 4 − 2 = 2 positions

• But here if we have used Horspool’s method shift would have been 3 positions
which is better choice. Hence we construct one more table called good suffix
table and choose best options for shift considering both table
20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 39
• If t1(c) − k ≤ 0, we obviously do not want to shift the pattern by 0 or a
negative number of positions. Rather, we can fall back on the brute-
force thinking and simply shift the pattern by one position to the
right.
• To summarize, the bad-symbol shift d1 is computed by the Boyer-
Moore algorithm either as t1(c) − k if this quantity is positive and as 1
if it is negative or zero. This can be expressed by the following
compact formula
• d1 = max{t1(c) − k, 1}.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 40

Constructing good suffix shift table
• Good suffix shift is calculated when there is another occurrence of
suff(k) in the pattern and there is another occurrence of suff(k)
not preceded by the same character as in its last occurrence.
• In this case, we can shift the pattern by the distance d2 between such
a second rightmost occurrence of suff(k) and its rightmost
occurrence. For example, for the pattern ABCBAB, these distances for
k = 1 and 2 will be 2 and 4, respectively:

• Good suffix shift (d2) is applied after 0<k<m last characters are
matched.
20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 41
• d2(k) is distance between last letter of matched suffix of size k and
last letter of its right most occurrences the pattern that is not
preceded by same character preceding the suffix.
• If there is no such occurrence, match the longest part (tail) of the k
character suffix with corresponding prefix.
• If there is no such suffix/prefix match, then d2(k)=m
• The complete list of the d2 values—the good-suffix table of the
Boyer-Moore algorithm—for the pattern ABCBAB

• Final pattern matching shift value d is

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 42
EXAMPLE : let us consider searching for the pattern BAOBAB in a text
made of English letters and spaces.
• The bad-symbol table looks as follows:

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 43

Text:
Pattern:

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 44

 The Boyer-Moore algorithm
• Step 1: For a given pattern and the alphabet used in both the pattern and the text,
construct the bad-symbol shift table.
• Step 2: Using the pattern, construct the good-suffix shift table .
• Step 3: Align the pattern against the beginning of the text.
• Step 4 : Repeat the following step until either a matching substring is found or the
pattern reaches beyond the last character of the text. Starting with the last character in
the pattern, compare the corresponding characters with the text character c until either
all m character pairs are matched (then stop) or a mismatching pair is encountered after
k ≥ 0 character pairs are matched successfully. In the latter case, retrieve the entry t1(c)
from the c’s column of the bad-symbol table where c is the text’s mismatched character.
If k > 0, also retrieve the corresponding d2 entry from the good-suffix table. Shift the
pattern to the right by the number of positions computed by formula

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 45

• The main difference between KMP algorithm and
Boyer-Moore Algorithm lies in the way they compare
characters of a pattern with their counterparts in a text:
• The KMP algorithm does it left to right, whereas the Boyer-
Moore algorithm does it right to left.
 The Knuth-Morris-Pratt algorithm
• KMP algorithm works in 2 steps
1. Prefix function for a pattern – Constructing ∏ table
2. KMP string matcher- Comparing text character with pattern character
using appropriate shift using ∏ table constructed in previous step.
Step 1: Prefix function for a pattern
The prefix function π for a pattern encapsulates knowledge about the
pattern so as to avoid unnecessary repeated comparison and supports
to perform appropriate shift while searching for the pattern in the text.
Also this avoids the pre-computation of δ performed for a string-
matching automaton.
We formalize the pre computation required as follows.
π[q] is the length of the longest prefix of P that is a proper suffix of Pq..
20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 24
Figure below gives the complete prefix function π for the pattern ababaca

i 1 2 3 4 5 6 7
P[i] a b a b a c a
∏[i] 0 0 1 2 3 0 1

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 25

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 26
Working of KMP algorithm for string matching
Text: bacbabababacaca, Pattern: ababaca
Initially construct Prefix table(∏ table), then follow steps given below
i 1 2 3 4 5 6 7
P[i] a b a b a c a
∏[i] 0 0 1 2 3 0 1

Step 1: Initialize i=1 and it is index to first character of text array and q=0 and it is index
previous to first character of pattern array
Step 2: if T[i] =P[q+1]
increment both i and q and repeat the previous step until q=m
if q=m print “ Pattern exists”
Else if q!=0
q=∏[q] and go to step 2
If q=0 increment i and go to step 2

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 27

 q=0,i=1 No matching
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

T b a c b a b a b a b a c a c a
P a b a b a c a

q=0,i=2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
b a c b a b a b a b a c a c a
a b a b a c a

q=1,i=3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
b a c b a b a b a b a c a c a
a b a b a c a
q=0,i=3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
b a c b a b a b a b a c a c a
20-12 -2023 Dr.P.V.Bh at, CS&Eng g, NMAMIT, Nitte 28
a b a b a c a
 q=0, i=4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
b a c b a b a b a b a c a c a
a b a b a c a

q=0,i=5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
b a c b a b a b a b a c a c a
a b a b a c a

q=∏(5)=3,i=10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
b a c b a b a b a b a c a c a
a b a b a c a
When q=7,i=14, q=m condition met, Therefore pattern exists at position i-m=14-7 = 7th position in the text

28
• Since q=7, the pattern has occurred with shift i-m=13-7=6
• The matching time of KMP – MATACHER is Ꝋ (n)

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 31

KMP Algorithms

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 32

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 33
Probabilistic Randomized Algorithms

• Randomized algorithms are algorithms that use random choices as part

of their logic.
• A randomized algorithm runs quickly but occasionally makes an error.
The probability of error can, however, be make negligibly small. Any
claimed solution can be verified efficiently for correctness.
• A randomized algorithm may give probabilistic answers which are not
necessarily exact.
• Randomized quicksort: This algorithm uses random coin tosses to
overcome the difficulty caused by an unhelpful input, such as a sorted or
reverse-sorted input.
• The best case and average case complexity of quick sort is in the order
n logn where as worst case complexity is in the order n2.
• The worst case occurs when input is already sorted.
Randomized quicksort
• Randomized quick sort chooses a random element as a
pivot. It is done so as to avoid the worst case of quick
sort in which the input array is already sorted.

• Randomly choosing the pivot element: Making the pivot

element a random variable is commonly used method in the
randomized quick sort. Here, even if the input is sorted, the
pivot is chosen randomly so the worst case time complexity
is avoided.

20-12-2023 Dr.P.V.Bhat, CS&Engg, NMAMIT, Nitte 46

 Description of quicksort

Quicksort is based on the divide-and-conquer paradigm.

Three-step divide-and-conquer process for sorting a typical subarray A[p.. r].

• Divide: Partition (rearrange) the array A[p .. r] into two subarrays

A[p… q - 1] and A[q + 1.. r] such that each element of A[p.. q - 1] is less than
or equal to A[q], which is, in turn, less than or equal to each element of
A[q + 1 ..r]. Compute the index q as part of this partitioning procedure.

• Conquer: Sort the two subarrays A[p .. q -1] and A[q +1 .. r] by recursive
calls to quicksort.

• Combine: Since the subarrays are sorted in place, no work is needed to

combine them: the entire array A[p .. r] is now sorted.
Quick sort Procedure
Partition Procedure
An Example
 Randomized Quick sort
• we randomized our algorithm by explicitly permuting the
input. Instead of always using A[r] as the pivot, we will use a
randomly chosen element from the subarray A[p .. r].

• We do so by exchanging element A[r] with an element chosen

at random from A[p .. r]. This modification, in which we
randomly sample the range p,...,r, ensures that the pivot
element x = A[r] is equally likely to be any of the r - p + 1
elements in the subarray.
• Because the pivot element is randomly chosen, we expect the
split of the input array to be reasonably well balanced on
average.
• The changes to PARTITION and QUICKSORT are small. In the
new partition procedure, we simply implement the swap
before actually partitioning:
Randomized Quick sort

Thus Worst case complexity is made as O(nlog n) by randomizing pivot