kmp

O algoritmo Knuth Morris Pratt (KMP) é utilizado para encontrar substrings em strings.

Se a sua entrada for pequena, você pode utilizar o find da classe string do c++ (http://www.cplusplus.com/reference/string/string/find/).

Entretanto em muitos casos isso não é suficiente.

O algoritmo mais comum para procurar uma string é criar dois índices, um para navegar na string dada e outro para navegar na substring dada, a qual chamaremos de pattern.

Assim, você compara os dois caracteres, se for igual, você incrementa ambos até que o pattern tenha sido encontrado. Se for encontrado, então você volta o índice do pattern para 0 e volta o índice da string para uma posição a mais de onde o pattern foi encontrado.

Aqui tem um exemplo de código para essa estratégia: http://www.geeksforgeeks.org/searching-for-patterns-set-1-naive-pattern-searching/

Entretanto, suponha por exemplo o caso:

text = xxxxxxxxxyxxxxxxxxxyxxxxxxxxxy (são 3 sequências de 9 x´s e 1 y)

pattern = xxxxxxxxxx (x aparece 10 vezes)

Supondo n como sendo o tamanho do text e m o tamanho do pattern, esse algoritmo rodará:

n*(m-1) vezes. Pois o toda vez que falta um x para o padrão bater, ele compara com o y e o padrão não bate, logo, o índice do padrão volta pro início e o índice do text é incrementado apenas de 1.

O algoritmo KMP resolve esse problema em O(n).

Ideia

O kmp tem duas etapas, um pré-processamento do pattern, que é feito em O(m) e a busca do padrão em si que e é feita em O(n). Logo, seria O(m)+O(n). Como n é maior que m, podemos dizer que é O(n).

Para entender a principal ideia do KMP, veja por exemplo o que acontece com o seguinte exemplo:

text = anananonano

pattern = ananonano

No algoritmo "naive", comparamos primeiro text[0] com pattern[0]. Os valores são iguais. Portanto, comparamos text[1] com pattern[1], que também possui valores iguais. Esse processo vai até que ele compara text[4] com pattern[4]. Só que dessa vez, os valores (text[4]='a' e pattern[4]='o') serão diferentes. Então ele vai voltar o índice do text para a posição 1 e o índice do paterna para a posição 0. Mas perceba que o pattern existe no text a partir da posição 2. Ou seja, já fizemos comparações do índice 0 até o índice 4, mas com o algoritmo "naive", essas comparações são desperdiçadas. O KMP aproveita essas comparações evitando que elas ocorram novamente. Assim, ele não vai voltar o índice do text e nem vai voltar (nesse caso) o índice do pattern para 0. Nesse caso, quando a posição 4 for diferente, só precisaremos voltar o índice do "pattern" uma única posição (índice 3) e acrescentar uma posição ao índice do text. Assim, na próxima compararemos text[5] com pattern[3]:

text = anananonano

ˆ

pattern = ananonano

ˆ

Isso é possivel, porque a substring "ana" do text (posições 2 a 4) já foram "casadas" com as posições iniciais do pattern.

Para entender como o KMP faz isso, imagine todos os prefixos do paterna "ananonano":

0 {vazio}

1 a

2 an

3 ana

4 anan

5 anano

6 ananoa

7 ananoan

8 ananoano

Agora, vamos identificar, a partir de cada um dos elementos acima, todos os maiores prefixos que também são sufixos e que não formam a palavra original. Por exemplo, a palavra ABCAB, possui como maior prefixo e que também é sufixo a substring "AB". Então, para a lista acima, a nossa lista de maiores prefixos que também são sufixos é:

0 {vazio}

1 {vazio}

2 {vazio}

3 a

4 an

5 {vazio}

6 {vazio}

7 an

8 {vazio}

Suponha agora que estamos executando o kmp e encontramos um match com a substring "anan". Perceba que se houver um mismatch após no próximo caracter, a substring "an" será a próxima que você tentará fazer um match. A segunda lista que fizemos, serve justamente para isso, ou seja, o índice 4 da segunda lista, nos diz que no caso de um mismatch devemos retroceder no padrão para tentar casar com a substring "an" ('índice 2 da primeira lista). Se por acaso houver um mismatch, o índice 2 da segunda lista nos diz que não existe mais para onde retroceder a não ser para o início (veja que o valor está vazio no índice 2 da segunda lista).

Em outras palavras, o KMP constrói um autômato finito determinístico indicando para qual substring devemos retroceder no padrão.

Não é tão simples de perceber esse autômato. Então segue mais um exemplo. Suponha o paterna "nanon"

Lista de prefixos:

0 {vazio}

1 n

2 na

3 nan

4 nano

5 nanon

Lista de maiores prefixos que também são sufixos e que são diferentes da palavra original:

0 {vazio}

1 {vazio}

2 {vazio}

3 n

4 {vazio}

5 n

Pronto, com essa ideia em mente, o primeiro passo é construir esse autômato. Isso é feito na etapa de pré-processamento, cujo código em C++ é mostrado a seguir:

Pré-processamento:

/*

A ideia aqui é construir uma tabela que indique

para que índice do padrão você deve retornar

quando algum caracter for diferente.

*/

void pre_process()

{

    int i=0, j=-1; back_table[0] = -1;

     while (i < p_len)

     {

         while (j >= 0 && pattern[j] != pattern[i])

         {

             j = back_table[j];

         }

         i++;

         j++;

         back_table[i] = j;

     }

}

j >= 0 será falso, pois j é i. Logo:

i++;

j++;

back_table[i] = j;

Dessa vez no while, j é >=0:

while (j >= 0 && pattern[j] != pattern[i])

pattern[j] é 'n'

pattern[i] é 'a'

ou seja, são diferentes. Logo:

j = back_table[j];

j, passa a receber o valor de back_table[0], ou seja, j será -1.

Fazendo:

i++;

j++;

back_table[i] = j;

Temos:

Voltando ao loop: while (j >= 0 && pattern[j] != pattern[i])

j>=0 é true

pattern[j] é 'n' (j vale 0) e pattern[i] (i vale 2) também é 'n', ou seja, eles não são diferentes. Portanto, o loop não será executado.

Os próximos comandos são:

i++;

j++;

back_table[i] = j;

Analizando o loop: while (j >= 0 && pattern[j] != pattern[i])

j >= 0 é true

pattern[1] é 'a'

pattern[3] é 'o'

Logo, são diferentes. O loop é executado:

j = back_table[j];

j passará a ser back_table[1] que é 0.

Mais uma vez analizando o loop:

j >= 0 é true

pattern[0] é 'n'

pattern[3] é 'o'

Logo, são diferentes. O loop é executado:

j = back_table[j];

J passará a ser back_table[0] que é -1.

Agora analizando o loop, j>=0 é falso.

Os próximos comandos são:

i++;

j++;

back_table[i] = j;

i ainda vale 4, enquanto que p_len vale 5, portanto, o loop externo será executado mais uma vez (while (i < p_len))

Analizando o loop: while (j >= 0 && pattern[j] != pattern[i])

j >= 0 é true

pattern[0] é 'n'

pattern[3] é 'n'

Logo, são iguais. O loop não é executado:

Os próximos comandos são:

i++;

j++;

back_table[i] = j;

Dessa vez, i vale 5 e, portanto,

while (i < p_len)

será falso.

Uma vez o autômato construído, é hora de utilizá-lo para encontrar os padrões.

No código a seguir, percorremos o text comparando com os caracteres do pattern. Se o índice do pattern for igual ao seu tamanho, então conseguimos percorrer o autômato inteiro e, portanto, temos um match. Caso os caracteres do text e do pattern sejam diferentes, então voltamos a posição do índice do pattern para o valor indicado pela back_table, ou seja, seguimos a setinha do autômato que indica um retorno. Estude o código abaixo.

void kmp_search()

{

    int i=0, j=0;

    while (i < t_len)

    {

        while (j >=0 && text[i] != pattern[j] )

        {

            j = back_table[j];

        }

        ++i;

        ++j;

        if ( j == p_len )

        {

            printf("Encontrado na posição %d\n", i-j);

            j = back_table[j];

        }

    }

}

int main()

{

    strcpy(text, "nanonanonanxanon");

    strcpy(pattern, "nanon");

    t_len = strlen(text);

    p_len = strlen(pattern);   

    pre_process();   

    kmp_search();

    return 0;

}

Referências:

• http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
• https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/