Dimostrazione della correttezza della failure function

[Lauke]

Salve, perdonate il disturbo, vi volevo chiedere, se è possibile, un suggerimento.

Ripassando linguaggi mi sono reimbattuto nella failure function, esposta come segue

$t = 0$;
$f(1) = 0$;
for($s = 1$; $s < n$; $s++$) {
while($t>0$ && $b_{s+1} != b_{t+1}$) $t = f(t)$;
if($b_{s+1} == b_{t+1}$) {
$t = t+1$;
$f(s + 1) = t$;
}
else $f(s+1)=0$;
}

Un esercizio in particolare mi chiede di dimostrare tramite induzione su $s$ la correttezza dell'algoritmo.

Devo essere sincero non riesco a orientarmi granchè. Intanto non so bene cosa prendere come "contatore" dell'induzione, ho provato a prendere la lunghezza del prefissi propri/suffissi propri. Ma non ne vengo a capo.

In ogni caso a preescindere questo il caso base è banale se $s=1$ segue che $t=0$ per cui non si entra nel while e si va direttamente all'if. In questo si riesce a computare correttamente la failure function, banalmente...

Ora dovrei supporla vera per $s$ (cosa? però...) e vedere se vale per $s + 1$.

Non è che qualcuno ha un link verso la dimostrazione? O un suggerimento tanto per darmi un input sul come procedere.

Grazie

[Rggb1]

Mai affrontata direttamente, ma mi sembra che il nodo sia nel dimostrare cosa fa il ciclo while(). Direi di dimostrare per induzione su $s$ che il valore di $t$ è quello giusto.

[hamming_burst]

Non è che qualcuno ha un link verso la dimostrazione?

forse ti può essere utile, non conosco questa funzione (o assomiglia ad una funzione che conosco con nomi diversi), ma qua mostra i primi passi di una dimostrazione:

http://spazioinwind.libero.it/inginfotv ... nction.pdf

ciao