T03
Aggregazione dei criteri
Aperto: giovedì, 24 giugno 2021, 00:00
Data limite: martedì, 29 giugno 2021, 23:59
Considere nossos algoritmos para encontrar o segmento repetido mais longo em um string (implementados em LongestRepeatedSubstring.java e LongestRepeatedSubstringX.java). Seja \(s\) um string e suponha que $r$ seja o maior comprimento dos segmentos repetidos em $s$. Prove que, com entrada $s$, nossos algoritmos fazem, no mínimo, $r(r+1)/2$ comparações entre caracteres.