T03
Conditions d’achèvement
Ouvert le : jeudi 24 juin 2021, 00:00
À remettre : mardi 29 juin 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.