Os algoritmos para busca de partes de um texto (substring) em geral procuram pela ocorrência de uma
"palavra" W dentro de um "texto" S empregando a simples técnica de que quando aparece uma diferença, a palavra tem em si a informação necessária para determinar onde começar a próxima comparação. Um dos algoritmos mais conhecido é o KMP (Knuth-Morris-Pratt). (Cormen, T. H., Introdução aos Algoritmos). a) Elabore um programa em qualquer linguagem de programação que seja capaz de realizar a identificação de um padrão W dentro de um texto S, com complexidade O(n) no pior caso.b) A partir da cadeia de caracteres textuais ABACAABACCABACABAABB demonstre a pesquise do padrão ABACAB utilizando o método KMP, informando quantas comparações foram realizadas pelo método.
Rafaela está aguardando sua ajuda, Clique aqui para responder.
Mais perguntas de Informática
Informática
A informática é uma área em constante evolução e desenvolvimento. Para aproveitar ao máximo os benefícios desta área, é importante manter-se...
vitoriaheleen - há 2 anos
Informática
A informática é uma área importante que está cada vez mais presente em nossas vidas. Se você deseja aprender mais sobre ela, aqui estão algumas...
Jsydhsjsksndbdhydehehehdhhdh - há 2 anos
Informática
A informática é uma área em constante evolução, com novas tecnologias surgindo a todo momento. Para se manter informado e atualizado, é...
Gabrielpereira Caio - há 2 anos
Informática
A informática é a ciência que estuda o armazenamento, a recuperação, a transmissão e a manipulação de informações. Ela se baseia na...
Jjjjkkkkk - há 2 anos
Informática
A Informática é uma área de conhecimento que se dedica ao estudo, aplicação e desenvolvimento de tecnologias de computação. Ela abrange diversas...
RafaelLima Tainaraie - há 2 anos
Informática
A informática é uma área de estudo que abrange a tecnologia da computação e seus usos na vida cotidiana. Ela está envolvida em quase todos os...
Gui Alisont Alison - há 2 anos
Informática
