T03
Condições de conclusão
Aberto: quinta-feira, 24 jun. 2021, 00:00
Vencimento: terça-feira, 29 jun. 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.