Busca de substring

Livro de Sedgewick e Wayne: parte da sec.5.3, p.758. Website do livro: resumo sec.5.3, slides. Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.princeton.edu/code/.

O problema substring search consiste em encontrar uma dada string dentro de outra maior. Por exemplo, encontrar canoeiro em

QUINCAS BORBA Machado de Assis CAPÍTULO I
RUBIÃO fitava a enseada, -- eram oito horas da 
manhã. Quem o visse, com os polegares metidos no
cordão do chambre, à janela de uma grande casa 
de Botafogo, cuidaria que ele admirava aquele
pedaço de água quieta; mas, em verdade, vos digo
que pensava em outra coisa. Cotejava o passado
com o presente. Que era, há um ano? Professor.
Que é agora? Capitalista! Olha para si, para as
chinelas (umas chinelas de Túnis, que lhe deu
recente amigo, Cristiano Palha), para a casa,
para o jardim, para a enseada, para os morros e
para o céu; e tudo, desde as chinelas até o céu,
tudo entra na mesma sensação de propriedade. 
-- Vejam como Deus escreve direito por linhas
tortas, pensa ele. Se mana Piedade tem casado
com Quincas Borba, apenas me daria uma esperança
colateral. Não casou; ambos morreram, e aqui
está tudo comigo; de modo que o que parecia uma
desgraça... CAPÍTULO II QUE abismo que há entre
o espírito e o coração! O espírito do 
ex-professor, vexado daquele pensamento,
arrepiou caminho, buscou outro assunto, uma
canoa que ia passando; o coração, porém, deixou-
se estar a bater de alegria. Que lhe importa a
canoa nem o canoeiro, que os olhos de Rubião 
acompanham, arregalados? Ele, coração, vai
dizendo que, uma vez que a mana Piedade tinha de
morrer, foi bom que não casasse; podia vir um
filho ou uma filha... 
-- Bonita canoa! 
-- Antes assim! 
-- Como obedece bem aos remos do homem! 
-- O certo é que eles estão no céu!

Esta página discute um algoritmo inocente (de força bruta) para o problema. Algoritmos mais sofisticados são discutidos nas páginas seguintes.

Resumo:

terminologia e regras do jogo
algoritmo inocente (força bruta)
retrocesso durante a busca
queremos um algoritmo linear!

Introdução

Problema: Dada uma string pat e uma string txt, encontrar uma ocorrência de pat em txt.

Exemplo: Encontre ATTGG na string abaixo (ignorando as quebras de linha):

TGGTAAGCGGTTCCTGCCCCGGCTCAGGGCCAAGAACAGATGAGA
CAGCTGAGTGATGGGCCAAACAGGATATCTGTGGTAAGCAGTTCC
TGCCCCGGCTCGGGGCCAAGAACAGATGGTCCCCAGATGCGGTCC
AGCCCTCAGCAGTTTCTAGTGAATCATCAGATGTTTCCAGGGTGC
CCCAAGGACCTGAAAATGACCCTGTACCTTATTTGAACTAACCAA
TCAGTTCGCTTCTCGCTTCTGTTCGCGCGCTTCCGCTCTCCGAGC
TCAATAAAAGAGCCCACAACCCCTCACTCGGCGCGCCAGTCTTCC
GATAGACTGCGTCGCCCGGGTACCCGTATTCCCAATAAAGCCTCT
TGCTGTTTGCATCCGAATCGTGGTCTCGCTGTTCCTTGGGAGGGT
CTCCTCTGAGTGATTGACTACCCACGACGGGGGTCTTTCATTTGG
GGGCTCGTCCGGGATTTGGAGACCCCTGCCCAGGGACCACCGACC
CACCACCGGGAGGTAAGCTGGCCAGCAACTTATCTGTGTCTGTCC
GATTGTCTAGTGTCTATGTTTGATGTTATGCGCCTGCGTCTGTAC
TAGTTAGCTAACTAGCTCTGTATCTGGCGGACCCGTGGTGGAACT
GACGAGTTCTGAACACCCGGCCGCAACCCTGGGAGACGTCCCAGG
GACTTTGGGGGCCGTTTTTGTGGCCCGACCTGAGGAAGGGAGTCG
ATGTGGAATCCGACCCCGTCAGGATATGTGGTTCTGGTAGGAGAC
GAGAACCTAAAACAGTTCCCGCCTCCGTCTGAATTTTTGCTTTCG
GTTTGGAACCGAAGCCGCGCGTCTTGTCTGCTGCAGCATCGTTCT
GTGTTGTCTCTGTCTGACTGTGTTTCTGTATTTGTCTGAAAATTA
GGGCCAGACTGTTACCACTCCCTTAAGTTTGACCTTAGGTCACTG
GAAAGATGTCGAGCGGATCGCTCACAACCAGTCGGTAGATGTCAA
GAAGAGACGTTGGGTTACCTTCTGCTCTGCAGAATGGCCAACCTT
TAACGTCGGATGGCCGCGAGACGGCACCTTTAACCGAGACCTCAT
CACCCAGGTTAAGATCAAGGTCTTTTCACCTGGCCCGCATGGACA
CCCAGACCAGGTCCCCTACATCGTGACCTGGGAAGCCTTGGCTTT
TGACCCCCCTCCCTGGGTCAAGCCCTTTGTACACCCTAAGCCTCC
GCCTCCTCTTCCTCCATCCGCCCCGTCTCTCCCCCTTGAACCTCC
TCGTTCGACCCCGCCTCGATCCTCCCTTTATCCAGCCCTCACTCC
TTCTCTAGGCGCCGGAATTCGTTAACTCGAGGATCCGGCTGTGGA
ATGTGTGTCAGTTAGGGTGTGGAAAGTCCCCAGGCTCCCCAGCAG
GCAGAAGTATGCAAAGCATGCATCTCAATTAGTCAGCAACCAGGT
GTGGAAAGTCCCCAGGCTCCCCAGCAGGCAGAAGTATGCAAAGCA
TGCATCTCAATTAGTCAGCAACCATAGTCCCGCCCCTAACTCCGC
CCATCCCGCCCCTAACTCCGCCCAGTTCCGCCCATTCTCCGCCCC
ATGGCTGACTAATTTTTTTTATTTATGCAGAGGCCGAGGCCGCCT
CGGCCTCTGAGCTATTCCAGAAGTAGTGAGGAGGCTTTTTTGGAG
GCCTAGGCTTTTGCAAAAAGCTGCCCAAGCTGATCCCCGGGGGCA
ATGAGATATGAAAAAGCCTGAACTCACCGCGACGTCTGTCGAGAA
GTTTCTGATCGAAAAGTTCGACAGCGTCTCCGACCTGATGCAGCT
CTCGGAGGGCGAAGAATCTCGTGCTTTCAGCTTCGATGTAGGAGG
GCGTGGATATGTCCTGCGGGTAAATAGCTGCGCCGATGGTTTCTA
CAAAGATCGTTATGTTTATCGGCACTTTGCATCGGCCGCGCTCCC
GATTCCGGAAGTGCTTGACATTGGGGAATTCAGCGAGAGCCTGAC
CTATTGCATCTCCCGCCGTGCACAGGGTGTCACGTTGCAAGACCT
GCCTGAAACCGAACTGCCCGCTGTTCTGCAGCCGGTCGCGGAGGC
CATGGATGCGATCGCTGCGGCCGATCTTAGCCAGACGAGCGGGTT
CGGCCCATTCGGACCGCAAGGAATCGGTCAATACACTACATGGCG
TGATTTCATATGCGCGATTGCTGATCCCCATGTGTATCACTGGCA
AACTGTGATGGACGACACCGTCAGTGCGTCCGTCGCGCAGGCTCT
CGATGAGCTGATGCTTTGGGCCGAGGACTGCCCCGAAGTCCGGCA
CCTCGTGCACGCGGATTTCGGCTCCAACAATGTCCTGACGGACAA
TGGCCGCATAACAGCGGTCATTGACTGGAGCGAGGCGATGTTCGG
GGATTCCCAATACGAGGTCGCCAACATCTTCTTCTGGAGGCCGTG
GTTGGCTTGTATGGAGCAGCAGACGCGCTACTTCGAGCGGAGGCA
TCCGGAGCTTGCAGGATCGCCGCGGCTCCGGGCGTATATGCTCCG
CATTGGTCTTGACCAACTCTATCAGAGCTTGGTTGACGGCAATTT
CGATGATGCAGCTTGGGCGCAGGGTCGATGCGACGCAATCGTCCG
ATCCGGAGCCGGGACTGTCGGGCGTACACAAATC

A string pat é conhecida como padrão (pattern) e txt é conhecida como texto.
Exemplo: procurando uma agulha num palheiro:
Aplicações:
- mecanismo find em um editor de texto,
- busca na Web por arquivos que têm uma certa palavra,
- busca padrões que indicam spam em email,
- hackers procurando pela palavra password no seu computador.

Regras do jogo

Parâmetros: M (comprimento de pat) e N (comprimento de txt). Em geral, M é pequeno e N é grande.
Notação: Nas discussões informais, imagine que as strings são vetores de caracteres. Assim, podemos escrever
- pat[j] em lugar de pat.charAt(j),
- pat[a..] em lugar de pat.substring(a),
- pat[a..b-1] em lugar de pat.substring(a,b).
Podemos dizer que o padrão é pat[0..M-1] e o texto é txt[0..N-1].
Dizemos que o padrão pat ocorre em txt, ou casa com txt, a partir de uma posição i se pat é igual a txt[i..i+M-1]. É claro que 0 ≤ i ≤ N-M.
Nosso problema: encontrar um índice a partir do qual pat casa com txt (ou constatar que tal índice não existe).
Leia A short history na página 759 do livro.

Exercícios 1

Qual a solução do problema se M == 0? Qual a solução do problema se M > N?
(SW 5.3.4) M brancos consecutivos. Escreva um método eficiente que receba uma string txt e um inteiro M como argumentos e devolva a posição da primeira ocorrência de M espaços em branco consecutivos em txt (ou devolva txt.length se não houver tal ocorrência). Estime o número de comparações de caracteres usado pelo seu método, em texto típico e no pior caso.
Quantas vezes o padrão abcab ocorre no texto xxxabcabcabxxxx ?

Algoritmo de força bruta

O algoritmo de força bruta (ou algoritmo inocente) compara pat com todas as substrings de txt.

Devolve um índice i tal que pat casa com txt a partir de i ou devolve N se tal índice não existe:

public static int search(String pat, String txt) {
   int j, M = pat.length();
   int i, N = txt.length();

   for (i = 0; i <= N - M; i++) {
      for (j = 0; j < M; j++)
         if (txt.charAt(i+j) != pat.charAt(j))
            break;
      if (j == M) return i;
   }
   return N;
}

Procurando o padrão ABRA no texto ABACADABRAC:
A busca pode ser lenta. Por exemplo, padrão AAAAB no texto AAAAAAAAAB:
O website do livro tem um programa Java animado (algs4.cs.princeton.edu/lectures/search.jar) que ilustra o funcionamento do método search.
Proposição M. No pior caso, o algoritmo de força bruta faz ~MN comparações entre caracteres. Prova: No pior caso, M (N − M + 1) comparações, e isso chega perto de MN quando M é menor que N.
Mas em geral o algoritmo é rápido: o número de comparações dificilmente passa de 1.1 N .

Outra maneira de escrever o código do algoritmo de força bruta:

public static int search(String pat, String txt) {
   int j, M = pat.length();
   int i, N = txt.length();

   for (i = 0, j = 0; i < N && j < M; i++) {
      if (txt.charAt(i) == pat.charAt(j)) j++;
      else { 
         i -= j; // retrocesso por sobre o texto
         j = 0; 
      }
   }
   if (j == M) return i - M;
   else return N;
}

Observações sobre essa versão alternativa:
- não é mais rápida que a primeira versão,
- os dois laços for da primeira versão se juntam num só,
- compara charAt(j) com charAt(i), não com charAt(i+j),
- parece fazer só N iterações, mas note o retrocesso (back up) de i sobre o texto,
- a forma é semelhante ao algoritmo KMP mais adiante.
Existe algoritmo mais rápido que o força bruta? Existe algoritmo que faz apenas N comparações entre caracteres? Existe algoritmo que faz menos que N comparações?

Exercícios 2

Quais são os invariantes da primeira versão do algoritmo de força bruta? Quais são os invariantes da segunda versão?
O método search de força bruta está correto quando M == 0? Está correto quando M > N?
(SW 5.3.16b) Faça um rastreamento do método search() de força bruta para o padrão A B A B A B A B e o texto A B A B A B A B A A B A B A B A B A A A A A A A A.
(SW 5.3.1) Escreva uma classe Java, digamos Brute, em torno do método search() de força bruta discutido acima.
(SW 5.3.15) Escreva uma versão searchRL do método search() que percorra o padrão da direita para a esquerda.
(SW 5.3.14) Escreva uma versão do método search() de força bruta que use vetores de caracteres em lugar do tipo String para representar o padrão e o texto.
(SW 5.3.7) Acrescente à implementação de força bruta um método count() que conte o número de ocorrências do padrão e um método searchAll() que imprima todas as ocorrências.
(SW 5.3.24.a) Todas as ocorrências. Escreva um método findAll() que encontre todas as ocorrêcias do padrão no texto.
(SW 5.3.28) Armazenamento temporário (buffering). Escreva um método search() que receba um fluxo de entrada (do tipo In) como argumento e procure um padrão pat no fluxo. Dica: Você precisa ter um buffer para guardar pelo menos os M caracteres anteriores do fluxo de entrada. O seu desafio é escrever código eficiente para inicializar, atualizar e esvaziar o buffer.