Class KMP

java.lang.Object
AEDs3.PatternMatching.KMP
public class KMP extends Object
A classe KMP implementa o algoritmo de Knuth-Morris-Pratt para busca de padrões em texto. Este algoritmo é eficiente para encontrar todas as ocorrências de um padrão em um texto, utilizando uma tabela de prefixos para otimizar a busca. A classe oferece métodos para construir a tabela de prefixos e realizar a busca em um fluxo de entrada binário, preservando o contexto ao redor do padrão encontrado.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    protected static class 
    KMP.MatchResult
    Classe interna que representa o resultado de uma ocorrência do padrão no texto.

  • Constructor Summary

    Constructors
    Constructor
    Description
    KMP()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static int[]
    buildPrefixTable(String pattern)
    Constrói a tabela de prefixo, também conhecida como LPS (Longest Prefix Suffix), que é utilizada pelo algoritmo de Knuth-Morris-Pratt para otimizar a busca.
    static boolean
    match(String pattern, String text)
    Verifica se um padrão está presente em um texto utilizando o algoritmo KMP.
    protected static List<KMP.MatchResult>
    searchInStream(InputStream inputStream, String pattern, int blockSize, int contextSize)
    Realiza a busca do padrão em um fluxo de entrada binário utilizando o algoritmo KMP com leitura em blocos.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • KMP

      public KMP()

  • Method Details

    • buildPrefixTable

      public static int[] buildPrefixTable(String pattern)
      Constrói a tabela de prefixo, também conhecida como LPS (Longest Prefix Suffix), que é utilizada pelo algoritmo de Knuth-Morris-Pratt para otimizar a busca.
      Parameters:
      pattern - O padrão a ser buscado no texto.
      Returns:
      Um array de inteiros contendo os comprimentos dos maiores prefixos próprios que também são sufixos para cada posição do padrão.

    • searchInStream

      protected static List<KMP.MatchResult> searchInStream(InputStream inputStream, String pattern, int blockSize, int contextSize) throws IOException
      Realiza a busca do padrão em um fluxo de entrada binário utilizando o algoritmo KMP com leitura em blocos. A busca é insensível a maiúsculas/minúsculas e preserva um contexto ao redor do padrão encontrado.
      Parameters:
      inputStream - Fluxo de entrada para leitura do arquivo binário.
      pattern - O padrão (palavra) a ser buscado no texto.
      blockSize - Tamanho do bloco de leitura em bytes.
      contextSize - Quantidade de caracteres de contexto a serem exibidos antes e depois do padrão encontrado.
      Returns:
      Uma lista de objetos MatchResult contendo as ocorrências encontradas.
      Throws:
      IOException - Se ocorrer um erro de leitura do arquivo.

    • match

      public static boolean match(String pattern, String text) throws IOException
      Verifica se um padrão está presente em um texto utilizando o algoritmo KMP. A busca é insensível a maiúsculas/minúsculas.
      Parameters:
      pattern - O padrão a ser buscado no texto.
      text - O texto onde o padrão será procurado.
      Returns:
      true se o padrão for encontrado no texto, false caso contrário.
      Throws:
      IOException - Se ocorrer um erro de leitura do fluxo de entrada.