Dimostrazione della correttezza della failure function
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
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
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.
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
