64
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 3keyboard_arrow_downkeyboard_arrow_up

Nesse exercício temos uma correspondência de cadeias baseada em fatores de repetição, onde y’ é a concatenação da cadeia y com ela mesma i vezes. O exercício é dividido em três itens, no primeiro vamos desenvolver um algoritmo que tenha como entrada um padrão para calcular o valor para .

Passo 2 de 3keyboard_arrow_downkeyboard_arrow_up

Para solucionar um problema que usa uma entrada e calcula podemos utilizar o algoritmo Naive-String-Matcher para resolver. Veja no algoritmo abaixo.

1 i = texto size();

2 m = padrão size();

3 for (a = 0 to n-m)

4 {

5 if (padrão[1..m] == texto[a+1 ... a+m])

6 return a;

7 add result(a);

8 }

Passo 3 de 3keyboard_arrow_downkeyboard_arrow_up

Com isso, temos um algoritmo eficiente que calcula os valores de P para qualquer i aleatório.

Por fim, o tempo de execução desse algoritmo seria . Isso porque uma parte de m vai para o loop “for na linha 3, e outra vai para o processo de verificação do “if na linha 5, pois o algoritmo é executado para o pior cenário.

Navegar por capítulo