Vamos a mais uma aula de dúvidas? E nesta aula vamos aprender a contar as ocorrências de uma substring dentro de uma string.

Vamos a um exemplo para facilitar a compreensão. Seja a frase “Quem ama, ama muito”. Se procurarmos pela substring “quais” nosso programa deve retornar zero, pois esta substring não ocorre na nossa string de exemplo. Contudo, ao procurarmos pela substring “ama” ele deve retornar 2, pois ela ocorre duas vezes em nossa string de exemplo.

Como já fizemos muitas vezes aqui no curso, precisamos dividir o problema em partes, isso irá facilitar a solução. Tentar identificar a quantidade de vezes que uma palavra (substring) ocorre em uma frase (string) pode ser complicado, então vamos tentar identificar uma ocorrência.

A função a seguir faz exatamente isso, busca se str2 ocorre em str1. O id é o índice a partir do qual iremos iniciar a busca. Inicialmente esse id será zero pois desejamos buscar a partir da primeira posição de str1. Precisamos de uma repetição para percorrer toda a string 1. Dentro dessa repetição iremos buscar pela ocorrência da primeira letra de str2. Enquanto não encontrarmos, ou seja, enquanto as letras de str1 forem diferentes da primeira letra de str2, a variável j recebe sempre zero.

Quando encontrarmos a primeira letra correspondente em str2 incrementamos a variável j em uma unidade. Se for a palavra procurada, as demais letras de str1 e str2 sempre serão iguais e, em algum momento, chegaremos ao final de str2 (que é a menor string). Precisamos verificar isso, por isso há um segundo if, onde verificamos se j é igual ao tamanho de str2. Se esse teste for verdadeiro significa que encontramos a primeira ocorrência de str2 em str1. Retornamos a variável i, que foi a última posição de str1 comparada com str2.

int existe(char *str1, char *str2, int id){
    int i, j = 0;

    for(i = id; i < strlen(str1); i++){
        if(str1[i] == str2[j])
            j++;
        else
            j = 0;
        if(j == strlen(str2))
            return i;
    }
    return -1;
}

Agora que temos uma função que nos diz se encontrou str2 em str1 ou não, basta controlar o índice onde inicia a comparação e conseguiremos descobrir a quantidade de ocorrências de str2 em str1.

Observe o código a seguir na função main. Dentro de uma repetição chamamos a função existe diversas vezes (enquanto o retorno for diferente de -1). Se o retorno for diferente de -1, significa que foi encontrado uma ocorrência de str2 em str1, então, basta chamar a função novamente, mas agora não iniciando a busca do início, mas a partir da última posição comparada (que temos, é o retorno da função).

int main(){
    char str1[] = "ama quem ama, ama muito!";
    char str2[] = "ama";
    int indice = 0, quantidade = 0;

    do{
        indice = existe(str1, str2, indice);
        printf("Retorno: %d\n", indice);
        if(indice != -1)
            quantidade++;
    }while(indice != -1);

    printf("\nQuantidade: %d\n", quantidade);

    return 0;
}

Código de exemplo completo em C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int existe(char *str1, char *str2, int id){
    int i, j = 0;

    for(i = id; i < strlen(str1); i++){
        if(str1[i] == str2[j])
            j++;
        else
            j = 0;
        if(j == strlen(str2))
            return i;
    }
    return -1;
}

int main(){
    char str1[] = "ama quem ama, ama muito!";
    char str2[] = "ama";
    int indice = 0, quantidade = 0;

    do{
        indice = existe(str1, str2, indice);
        printf("Retorno: %d\n", indice);
        if(indice != -1)
            quantidade++;
    }while(indice != -1);

    printf("\nQuantidade: %d\n", quantidade);

    return 0;
}