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

#Estrutura de dados

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

🤖 | 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;