T03
Abschlussbedingungen
Geöffnet: Donnerstag, 24. Juni 2021, 00:00
Fällig: Dienstag, 29. Juni 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.