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;
SOCIAL SHARE CARD GENERATOR