casamento de cadeias

Universidade Estadual de Mato Grosso do Sul
Bacharelado em Ciência da Computação
Algoritmos e Estruturas de Dados II

Tópicos
 Introdução
 Problema do casamento de cadeias
 Algoritmo da força bruta
 Algoritmo de Knuth, Morris e Pratt

 Exercícios

Introdução
 Cadeia: sequência de elementos chamados caracteres
 Caracteres pretencem a um alfabeto


Ex.: 0110010 é uma cadeia do alfabeto {0, 1}

 Comprimento de uma cadeia: quantidade de caracteres


Ex.: 0110010 é uma cadeia de comprimento 7

 Aplicações de cadeias de caracteres: processamento de

textos, dicionários, codificação de dados, sequenciamento de DNA, criptografia, etc.

Problema do casamento de cadeias  Sejam X e Y duas cadeias de comprimentos n e m,

respectivamente, onde n ≥ m
 X e Y estão armazenadas em vetores, onde xi e yi são tais

que 1 ≤ i ≤ n e 1 ≤ j ≤ m
 Y é subcadeia de X se Y é subsequência de elementos consecutivos de X




Nesse caso existe l ≤ n – m tal que xl+j = yj para todo 1 ≤ j ≤ m
Se l = 0, Y é um prefixo (próprio, se m ≠ n ) de X
Se l = n – m, Y é um sufixo (próprio, se m ≠ n ) de X

 Xk: subcadeia de X iniciando no índice k

Problema do casamento de cadeias  Problema do casamento de cadeias: Y é subcadeia de X?
 Caso seja, localizar Y em X: encontrar índice l


Nesse caso, houve um casamento de Y com X na posição l+1

 Ex. 1: X = baaabea e Y = aabe




Y é subcadeia de X l=2 Houve casamento de Y com X na posição 3

 Ex. 2: X = baaabea e Y = aeb


Y não é subcadeia de X

Problema do casamento de cadeias  Exemplo:

Algoritmo da força bruta
 Algoritmo da força bruta: verifica se Y é subcadeia de X

testando todas os possíveis valores para l
 Para l = 0, 1, ..., n – m, verificar se todos os caracteres de Y

são encontrados em X
 Caso Y seja encontrado em X, o algoritmo termina e o valor atual de l+1 é retornado

Algoritmo da força bruta
 Algoritmo:

Algoritmo da