KMP-Failure-Function

f	:	{1...\| m\|} $\displaystyle \to$ {0...\| m\| - 1}
		k $\displaystyle \mapsto$ max{i : 0 $\displaystyle \le$ i < k $\displaystyle \wedge$ m[1...i] = m[k - i + 1...k]}

Beispiel:

m a a b a b a a b

k 1 2 3 4 5 6 7 8

f 0 1 0 1 0 1 2 3

Rekonstruktion, Beispiel: ( $\Sigma$ = {a, b})

Johannes Waldmann 2008-01-24