Resenha critica e fichamento

AED´s III String Matching Casamento de Padrão
Professor: Ciro Meneses Santos

String Matching

O problema de localizar ocorrências de uma cadeia de caracteres em um texto.

UNIPAC – Universidade Presidente Antonio Carlos Departamento de Ciência da Computação

Introdução Conteúdo
• String Matching
– Algoritmo de Força Bruta

– Algoritmo KMP
– Algoritmo Boyer-Moore

• O problema de localizar ocorrência duma cadeia de caracteres num texto é muito frequente. Existem muitos algoritmos com qualidades diferentes para satisfazer esta necessidades. • O problema pode ser formulado como: dado um conjunto de símbolos “” que definimos como alfabeto do Texto. Desejamos saber as ocorrências do Padrão “P” no Texto “T”. • Aplicações:
– – – – Busca na Internet Busca de palavra em texto Verificações em sequências de DNA Livros, dicionários, artigos técnicos, científicos jornalismo

e

Introdução
• • • • • • • Notações: T  Texto; P  Padrão;   Alfabeto; n  Tamanho do Texto; m  Tamanho do Padrão; c  Tamanho do alfabeto;

Algoritmo Força Bruta
• Descrição:
O algoritmo força bruta consiste em verificar, em todas as posições no texto entre 0 e n-m, se uma ocorrência do padrão existe ou não. Isto e feito deslocando o padrão sobre o texto por exatamente uma posição à direita.

• Características Principais:
– Nenhuma fase de pre-procesamento
– – – – E necessário espaço extra para constante desloca sempre o conteúdo 1 posição à direita As comparações podem ser feitas em qualquer ordem. A complexidade do Algoritmo e O(nm).

1

Algoritmo Força Bruta
• • • • Alfabeto = {a, b, c} Texto ={abaabacab} Padrão = { a a b a } Passos: abaabacab aaba  abaabacab aaba  abaabacab aaba  Primeira tentativa ABAABAC AB
1 2

Algoritmo Força Bruta
Primeira tentativa GCAT C GC AGAGAGT AT ACAGT ACG 1 2 3 4 GCAGAGAG Em segundo tentativa GC AT C GC AGAGAGT AT ACAGT ACG 1 GCAGAGAG Terceira tentativa GCAT C GC AGAGAGT AT ACAGT ACG 1 GCAGAGAG

AA B A

Algoritmo Força