Z-Algorithmus – Beispiel
k = 2 : Fall 1
a a a b a a a a b a a
a a a b a a a a b a a
`, r
j
`j
rj
Zj
2
1
1
2
3
2
3
4
5
6
R. Stiebe: Textalgorithmen, WS 2003/04
7
8
9
10
11
1
Z-Algorithmus – Beispiel
k = 3 : Fall 2, k 0 = 2 → Fall 2c
a a a b a a a a b a a
a a a b a a a a b a a
`
j
`j
rj
Zj
2
1
1
2
3
2
3
1
r
4
3
3
5
6
R. Stiebe: Textalgorithmen, WS 2003/04
7
8
9
10
11
2
Z-Algorithmus – Beispiel
k = 4 : Fall 1
a a a b a a a a b a a
a a a b a a a a b a a
`, r
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
6
R. Stiebe: Textalgorithmen, WS 2003/04
7
8
9
10
11
3
Z-Algorithmus – Beispiel
k = 5 : Fall 1
a a a b a a a a b a a
a a a b a a a a b a a
`, r
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
6
5
7
R. Stiebe: Textalgorithmen, WS 2003/04
7
8
9
10
11
4
Z-Algorithmus – Beispiel
k = 6 : Fall 2, k 0 = 2 → Fall 2b
a a a b a a a a b a a
a a a b a a a a b a a
`
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
r
6
5
7
6
R. Stiebe: Textalgorithmen, WS 2003/04
7
6
11
8
9
10
11
5
Z-Algorithmus – Beispiel
k = 7 : Fall 2, k 0 = 2 → Fall 2a
a a a b a a a a b a a
a a a b a a a a b a a
`
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
6
5
7
6
R. Stiebe: Textalgorithmen, WS 2003/04
r
7
6
11
2
8
6
11
9
10
11
6
Z-Algorithmus – Beispiel
k = 8 : Fall 2, k 0 = 3 → Fall 2a
a a a b a a a a b a a
a a a b a a a a b a a
`
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
6
5
7
6
R. Stiebe: Textalgorithmen, WS 2003/04
r
7
6
11
2
8
6
11
1
9
6
11
10
11
7
Z-Algorithmus – Beispiel
k = 9 : Fall 2, k 0 = 4 → Fall 2a
a a a b a a a a b a a
a a a b a a a a b a a
`
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
6
5
7
6
R. Stiebe: Textalgorithmen, WS 2003/04
r
7
6
11
2
8
6
11
1
9
6
11
0
10
6
11
11
8
Z-Algorithmus – Beispiel
k = 10 : Fall 2, k 0 = 5 → Fall 2c
a a a b a a a a b a a
a a a b a a a a b a a
`
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
6
5
7
6
R. Stiebe: Textalgorithmen, WS 2003/04
r
7
6
11
2
8
6
11
1
9
6
11
0
10
6
11
2
11
10
11
9
Z-Algorithmus – Beispiel
k = 11 : Fall 2, k 0 = 2 → Fall 2c
a a a b a a a a b a a
a a a b a a a a b a a
j
`j
rj
Zj
2
1
1
2
3
2
3
1
4
3
3
0
5
4
4
3
6
5
7
6
R. Stiebe: Textalgorithmen, WS 2003/04
7
6
11
2
`
r
8
6
11
1
9
6
11
0
10
6
11
2
11
10
11
1
10

Beispiel: Wu-Manber