Leia duas cadeias de caracteres A e B. Determine quantas vezes a cadeia A ocorre na cadeia B.

Passo 1

O enunciado pede para contar quantas vezes uma string A aparece dentro de outra string B (pode haver sobreposições). O conteúdo é correspondência de padrões (string matching) e vamos usar a técnica de varrer B com uma janela de tamanho |A| e comparar substrings.

Passo 2

Sejam m = |A| e n = |B|. Se m > n, não há como A caber em B, logo a resposta é 0.
Inicialize um contador count = 0. Percorra todos os índices i de 0 até n – m (inclusive). Em cada posição i extraia a substring de B que vai de i até i + m – 1 e compare com A.
Sempre que B[i…i + m – 1] for igual a A, incremente count em 1. Este procedimento leva tempo O(m) para cada comparação, total O((n–m+1)·m) no método ingênuo.
Ao final do laço, count conterá exatamente o número de ocorrências (incluindo as sobrepostas) de A dentro de B.

Resposta

O número de ocorrências de A em B é dado por count = sumi=0^|B|-|A| [Bii+|A|-1=A], obtido pelo algoritmo acima.

Exercícios relacionados