Algorithms
Matrix & String
Partha Pratim Das
Department of Computer Science and Engineering
Indian Institute of Technology, Kharagpur
ppd@[Link]
T10KT Coordinators’ Workshop
March 18, 2015
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 1 / 10
String Matching Problem and Terminology
Given a text array and a pattern array
such that the elements of and are
characters taken from alphabet . e.g.,
or .
The String Matching Problem is to find all the occur-
rence of in .
A pattern occurs with shift in , if
= . The String Matching Problem
is to find all values of . Obviously, we must have
"
! ! .
T b a c a b c a b c a ...
s=2
P c a b c
2
String Matching Problem and Terminology
A string is a prefix of if = y, for some string
Similarly, a string is a suffix of if =y , for
some string .
3
Brute Force Algorithm
Initially, is algined with at the first index position.
is then compared with from left-to-right. If a
mismatch occurs, ”slide” to right by 1 position, and
start the comparison again.
T c a c a b c a c a b c a c a b
s=0
s=1 s=2
P c a b c a b c a b
4
Brute Force Algorithm
BF_StringMatcher(T, P) {
n = length(T);
m = length(P);
// s increments by 1 in each iteration
// => slide P to right by 1
for (s=0; s<=n-m; s++) {
// starts the comparison of P and T again
i=1; j=1;
while (j<=m && P[s+i]==T[j]) {
// corresponds to compare P and T from
// left-to-right
i++; j++;
}
if (j==m+1)
print "Pattern occurs with shift=", s
}
}
5
The Knuth-Morris-Pratt (KMP) Algorithm
In the Brute-Force algorithm, if a mismatch occurs at
( ), it only slides to right by 1 step. It
throws away one piece of information that we’ve al-
ready known. What is that piece of information ?
Let be the current shift value. Since it is a mismatch
" "
at , we know .
s+1 s+j−1
T ...
.....
s
P
1 j
How can we make use of this information to make the
next shift? In general, should slide by such
that = . We then compare
with .
6
The Knuth-Morris-Pratt (KMP) Algorithm
When we slide to right, it should be a place where
could possibly occur in .
T b a c b a b a b a a b c b a b
s
P a b a b a c a
1 q
T b a c b a b a b a a b c b a b
s’
P a b a b a c a
1 k
1 q
a b a b a P[1..q]
a b a P[1..k] is a suffix of P[1..q]
1 k
7
Do not shift too much
Do not shift too much, as it may miss some matched
patterns!
T a b a b a b a b c
s
P a b a b a b c
T a b a b a b a b c
It shifts too much! A matched pattern is missed.
s’=s+4
P a b a b a b c
T a b a b a b a b c
s’=s+2
P a b a b a b c
8
The next function
We need to answer the following question: Given
match text characters , what is the
least shift such that
= ?
In practice, the shift can be precomputed by com-
paring against itself. Observe that
is a known text, and it is a suffix of . To find
the least shift , it is the same as finding the
largest , s.t.,
is a suffix of .
9
The next function
Given , let next be a function
"
such that
next(q) and is a suffix of
.
q 1 2 3 4 5 6 7 8 9 10
P[q] a b a b a b a b c a
next(q) 0 0 1 2 3 4 5 6 0 1
Given next(q) for all ! ! , we can use the KMP
algorithm.
10
The Knuth-Morris-Pratt (KMP) Algorithm
KMP_StringMatcher(T, P) {
n = length(T); m = length(P);
compute_Next(P);
q = 0; // number of characters matched
// so far
i=1;
while (i<=n) {
// loop until a match is found, or
// number of characters matched so far
// is 0; // note ’i’ is unchanged.
while (q > 0 and P[q+1] != T[i]) {
q=next[q];
}
// matched character increased by 1
if (P[q+1]==T[i]) q=q+1;
if (q==m) {
print "Pattern occurs with shift=", i-m
q=next[q];
}
i++;
}
}
11
How to compute next function
We first set , then compute
with
"
, one by one in iterations.
compute_Next(P) {
m = length(P);
next[1]=0;
k = 0; // number of characters matched
// so far
q=2;
while (q<=m) {
while (k > 0 and P[k+1] != P[q]) {
k = next[k];
}
if (P[k+1]==P[q]) k=k+1;
next[q]=k;
q++;
}
}
12
Running Time of the KMP Algorithm
1. compute Next
" "
(a) at the beginning, and !
at all times.
"
(b) Note that after each comparison, in-
"
creases at least by 1. But the value of
starts at , and the largest possible value is
, it implies there are number of com-
parisons.
(c) Hence, the running time of compute Next is
.
2. KMP StringMatcher
" "
(a) at the beginning, and !
at all times.
14
"
(b) Note that after each comparison, in-
creases at least by 1.
(c) Hence, the running time of KMP StringMatcher
.
Problem
Matrices
Efficient Matrix Multiplication
Matrix Chain Product
Finding Shortest Paths
Transitive Closure of a Graph
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 15 / 10
Problem
Transitive Closure of Binary Relations
How can one represent a binary relation in matrix notation?
Give a simple algorithm to find the transitive closure of a binary
relation? Explain its time complexity.
Transitive Closure of the adjacency relation for a graph is called as
reachability relation. Give an overview to compute the reachability
relation for a digraph.
Can you improve the complexity of the algorithm?
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 16 / 10
Problem
Transitive Closure of Binary Relations
How can one represent a binary relation in matrix notation?
S is a set and R is a binary relation over it. Assume |S| = n.
Elements of S are made nodes of a digraph, G .
If element x is related to element y (x R y ), connect Nx to Ny in G
Represent G in its (boolean) adjacency matrix A
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 17 / 10
Problem
Transitive Closure of Binary Relations
Give a simple algorithm to find the transitive closure of a binary
relation? Explain its time complexity.
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 18 / 10
Problem
Transitive Closure of Binary Relations
Transitive Closure of the adjacency relation for a graph is called as
reachability relation. Give an overview to compute the reachability
relation for a digraph.
Let A0 = A. Compute a series of matrix products as: A1 = A0 ∗ A, A2
= A1 ∗ A, A3 = A2 ∗ A, · · · (boolean multiplication). If x R y and
y R z (in A), x R z in A1 . Further if z R w (in A), x R w in A2 , and
so on.
Note that An = An−1 . In fact, the fix-point can happen earlier too.
A∗ = A0 + A1 + A2 + · · · + An (boolean addition) is the transitive
closure (all paths in G ) of relative S.
Cost = O(n4 )
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 19 / 10
Problem
Transitive Closure of Binary Relations
Can you improve the complexity of the algorithm?
A path exists between two vertices i to i, iff
there is an edge from i to j; or
there is a path from i to j going through vertex 1; or
there is a path from i to j going through vertex 1 and/or 2; or
there is a path from i to j going through vertex 1, 2, and/or 3; or
···
there is a path from i to j going through any of the other vertices
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
1 0 0 1
1 0 1 1
1 0 1 1
1 0 1 1
1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
R0 R1 R2 R3 R4
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 20 / 10
Problem
Transitive Closure of Binary Relations
On the k th iteration, the algorithm determine if a path exists between two
vertices i, j using just vertices among 1, · · · , k allowed as intermediate
R (k−1) [i, j] (path using just 1, · · · , k − 1)
R (k) [ij] = or
(R (k−1) [i, k] (path from i to k and from k
and to i using just 1, · · · , k − 1)
R (k−1) [k, j])
Partha Pratim Das (IIT, Kharagpur) Matrix & String March 18, 2015 21 / 10
Doubly Connected Edge List (DCEL)
• DCEL is one of the most commonly used
representations for planar subdivisions such as
Voronoi diagrams.
• It is an edge‐based structure which links together the
three sets of records:
– Vertex
– Edge
– Face
• It facilitates traversing the faces of planar
subdivision, visiting all the edges around a
given vertex