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

Risposte
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 :-)

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.