image

Acesse bootcamps ilimitados e +650 cursos

50
%OFF
Article image
Isadora Ariane
Isadora Ariane26/11/2024 14:09
Compartilhe

TOP 25 ALGORITMOS | Knuth-Morris-Pratt (KMP) Array

    Este algoritmo é um algoritmo de busca de strings que é usado para encontrar um padrão dentro de textos grandes de forma eficiente. Ao contrário do algoritmo de busca de padrões ingênuos que começa do início do padrão após cada incompatibilidade, o KMP usa a estrutura do padrão para evitar comparações redundantes. Ele pré-processa a string do padrão e cria uma matriz chamada matriz Longest Prefix Suffix (lps) que indica quanto do padrão pode ser reutilizado após uma incompatibilidade.

    📁 | Resumo

    image

    image

    image

    🤖 | Código

    .
    function constructLps(pat, lps) {
      
      // len armazena o comprimento do prefixo mais longo que também é um sufixo para o índice anterior
      let len = 0;
    
    
      // lps[0] é sempre 0
      lps[0] = 0;
    
    
      let i = 1;
      while (i < pat.length) {
          
          // Se os caracteres corresponderem, incremente o tamanho de lps
          if (pat[i] === pat[len]) {
              len++;
              lps[i] = len;
              i++;
          }
          
          // Se houver uma incompatibilidade
          else {
              if (len !== 0) {
                  
                  // Atualiza len para o valor lps anterior para evitar comparações redundantes
                  len = lps[len - 1];
              } else {
                  
                  // Se nenhum prefixo correspondente for encontrado, defina lps[i] como 0
                  lps[i] = 0;
                  i++;
              }
          }
      }
    }
    
    
    function search(pat, txt) {
      const n = txt.length;
      const m = pat.length;
    
    
      const lps = new Array(m);
      const res = [];
    
    
      constructLps(pat, lps);
    
    
      // Ponteiros i e j, para percorrer o texto e o padrão
      let i = 0;
      let j = 0;
    
    
      while (i < n) {
          
          // Se os caracteres corresponderem, mova ambos os ponteiros para frente
          if (txt[i] === pat[j]) {
              i++;
              j++;
    
    
              // Se o padrão inteiro for correspondido armazena o índice inicial no resultado
              if (j === m) {
                  res.push(i - j);
                  
                  // Utiliza o LPS do índice anterior para pula comparações desnecessárias
                  j = lps[j - 1];
              }
          }
          
          // Se houver uma incompatibilidade
          else {
              
              // Use o valor lps do índice anterior para evitar comparações redundantes
              if (j !== 0)
                  j = lps[j - 1];
              else
                  i++;
          }
      }
      return res; 
    }
    .
    

    🕰️ | Complexidade de Tempo

    Como N é o comprimento do texto e M é o comprimento do padrão. Isso ocorre porque criar o array LPS (Longest Prefix Suffix) leva tempo O(M), e a busca pelo texto leva tempo O(N). Logo, a complexidade de tempo será O(N + M).

    📦 | Complexidade de Espaço

    Como há necessidade de espaço temporário auxiliar, a complexidade de espaço será O(M).

    ✔️ | Vantagens

    ✦ Eficiente;

    ❌ | Desvantagens

    ✦ Nada intuitivo e nada fácil de implementar;

    Compartilhe
    Comentários (0)