CASAMENTO EXATO DE CADEIAS DE CARACTERES
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS
FACULDADE DE COMPUTAÇÃO
CASAMENTO EXATO DE CADEIAS DE CARACTERES
Belém/PA
2013
CASAMENTO EXATO DE CADEIAS DE CARACTERES
Belém/PA
2013
SUMÁRIO
1 INTRODUÇÃO
Casamento de padrões é o ato de verificação da presença de um padrão em um conjunto de dados. Em contraste ao reconhecimento de padrões, o padrão é rigidamente especificado, seja por uma cadeia de caracteres ou uma árvore. As cadeias aparecem no processamento de textos em linguagem natural, códigos, dicionários, sequenciamento de DNA em biologia computacional, representação de imagens por meio de bitmaps, dentre outros.
O casamento de padrões é usado para testar se o objeto de estudo possui a estrutura desejada, para então encontrar a estrutura relevante, encontrar os pontos de alinhamento e substituir a parte do casamento por outra estrutura. Padrões de sequência (como cadeias de texto) são geralmente escritos usando expressões regulares.
Uma cadeia corresponde a uma sequência de elementos denominados caracteres. Os caracteres são escolhidos de um conjunto denominado alfabeto. Por exemplo, em uma cadeia de bits o alfabeto é {0, 1}.
A pesquisa em cadeias de caracteres é um componente importante em diversos problemas computacionais, tais como edição de