30

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.597

Passo 1 de 3keyboard_arrow_downkeyboard_arrow_up

O exercício proposto pede o calculo da função prefixo para um padrão P = ababbabbabbababbabb. Para isso podemos construir um algoritmo com Knuth-Morris-Pratt que nos dê o resultado.

Passo 2 de 3keyboard_arrow_downkeyboard_arrow_up

O algoritmo que descreve a solução do problema proposto é

int* funcao_prefixo(char *padrao)

{

int m = strlen(padrao);

int *proximo = (int*)malloc(m*sizeof(int));

proximo[0]=0;

int k = 0;

int q;

for(q = 1;q < m;q++)

{

while(k > 0 && (padrao[k] != padrao[q]) )

k = proximo[k-1];

if (padrao[k] == padrao[q])

k++;

proximo[q] = k;

}

return proximo;

}

int KMP_match(char *texto,char *padrao)

{

int n = strlen(texto);

int m = strlen(pad rao);

int *proximo = funcao_prefixo(padrao);

int q = 0;

int i;

for(i = 0;i < n;i++)

{

while(q > 0 && (padrao[q] != texto[i]) )

q = proximo[q-1];

if (padrao[q] == texto[i])

q++;

if(q == m)

return i+1-m;

}

free(proximo);

return -1;

}

int main()

{

char *s1 = " ababbabbabbababbabb ";

char *s2 = "ababbab";

int funcao = KMP_match(s1,s2);

printf("funcao é %d\n",funcao);

return 0;

}

Passo 3 de 3keyboard_arrow_downkeyboard_arrow_up

Executando o algoritmo podemos encontrar a função prefixo de para qualquer padrão. Para o padrão P do nosso exercício obtemos a função prefixo como

.

Navegar por capítulo

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.