String Matching

Using Finite Automata

1
Example (I)

Q is a finite set of states

q0  Q is the start state 1
Q is a set of accepting sates
: input alphabet 0
: Q    Q: transition function States
2

4
3

input: a b a b b a b b a a

2
Example (II)

Q is a finite set of states

q0  Q is the start state 1
Q is a set of accepting sates
: input alphabet 0
: Q    Q: transition function States
2
input

state a b
4
0 1 0 3
1 1 2

2 1 3

3 4 0

4 1 2
3
Example (III)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3

3 4 0

4 1 2
4
Example (IV)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0
4 1 2
5
Example (V)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1
4 1 2
6
Example (VI)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1 2
4 1 2
7
Example (VII)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1 2 1
4 1 2
8
Example (VIII)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1 2 1 2
4 1 2
9
Example (IX)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1 2 1 2 3
4 1 2
10
Example (X)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1 2 1 2 3 4
4 1 2
11
Example (XI)

Q is a finite set of states a

q0  Q is the start state b a 1
Q is a set of accepting sates b
: input alphabet 0
a
: Q    Q: transition function a
2
input
b b
state a b
4 b
0 1 0 3
a
1 1 2

2 1 3
a b a b b a b b a a

3 4 0
0 1 2 1 2 3 4 2 3 4 1
4 1 2
12
Finite-Automaton-Matcher

 The example automaton accepts at the end of occurrences of the

pattern abba
 For every pattern of length m there exists an automaton with m+1
states that solves the pattern matching problem with the following
algorithm:

Finite-Automaton-Matcher(T,,P)
1. n  length(T)
2. q  0
3. for i  1 to n do
4. q  (q,T[i])
5. if q = m then
6. si-m
7. return “Pattern occurs with shift” s
13
Computing the Transition Function:
The Idea!

m a n a m a m a p a t i p i t

m a m a

m a m a

m a m a

m a m a

m a m a

m a m a

m a m a

14
How to Compute the Transition Function?

 A string u is a prefix of string v if there exists a string a such that:

ua = v
 A string u is a suffix of string v if there exists a string a such that:
au = v
 Let Pk denote the first k letter string of P

Compute-Transition-Function(P, )
1. m  length(P)
2. for q  0 to m do
3. for each character a   do
4. k  1+min(m,q+1)
5. repeat
k  k-1
6. until Pk is a suffix of Pqa
7. (q,a)  k
15
Example

 A string u is a prefix of string v if there

exists a string a such that: ua = v
 A string u is a suffix of string v if there
exists a string a such that: au = v
 Let Pk denote the first k letter string of P Pattern

a b a a b a a a a
Compute-Transition-Function(P, )
1. m  length(P) Text a b a a b a a a P7a
2. for q  0 to m do
3. for each character a   do a b a a b a a a P8
4. k  1+min(m,q+1)
5. repeat
k  k-1
6. until Pk is a suffix of Pqa
7. (q,a)  k
8.

16
Example

 A string u is a prefix of string v if there Pattern

exists a string a such that: ua = v
 A string u is a suffix of string v if there a b a a b a a a a
exists a string a such that: au = v
 Let Pk denote the first k letter string of P Text a b a a b a a b P7b

Compute-Transition-Function(P, ) a b a a b a a a P8
1. m  length(P)
2. for q  0 to m do a b a a b a a P7
3. for each character a   do
4. k  1+min(m,q+1) a b a a b a P6
5. repeat
k  k-1 a b a a b P5
6. until Pk is a suffix of Pqa
7. (q,a)  k
8.

17
Running time of Compute Transition-Function

 A string u is a prefix of string v if there

exists a string a such that: ua = v
 A string u is a suffix of string v if there
exists a string a such that: au = v
 Let Pk denote the first k letter string of P
Factor: m+1
Compute-Transition-Function(P, )
1. m  length(P)
Factor: ||
2. for q  0 to m do
3. for each character a   do
4. k  1+min(m,q+1) Factor: m
5. repeat
k  k-1
6. until Pk is a suffix of Pqa Time for check
of equality: m
7. (q,a)  k
8.
Running time of procedure:
O(m3 || )
18