T03
Completion requirements
Opened: Thursday, 24 June 2021, 12:00 AM
Due: Tuesday, 29 June 2021, 11:59 PM
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.