Algoritmos Paralelos para Casamento de Cadeias

Este trabalho trata de algoritmos paralelos para resolver o problema denominado Casamento de Cadeias (String-Matching) . Trata-se de um caso particular do problema de Casamento de Padrões (pattern-matching), que resume-se em procurar, num dado tipo de estrutura, um padrão, com o qual um subconjunto da estrutura se identifica.

Em particular, trata do caso em que tanto o padrão quanto a estrutura são cadeias de símbolos pertencentes a algum alfabeto.

São descritos os principais algoritmos paralelos para este problema, contidos na literatura. Descreve-se também o modelo de computação paralela para o qual todos esses algoritmos foram desenvolvidos, além dos limites inferiores para o problema.

Um dos algoritmos paralelos apresentados é modificado, no sentido de se obter a mesma complexidade num modelo mais fraco de computação paralela.

Porém, o algoritmo resultante funciona apenas para alguns casos especiais, contendo restrições sobre os tamanhos do alfabeto e do padrão.

Além disso, descreve-se brevemente os mais importantes algoritmos sequenciais para o problema.