Как подсчитать количество вхождений последовательности в строку?

Question

Напишите программу C, чтобы подсчитать количество вхождений последовательности «abc» во входной строке. Однако между (a и b) или (b и c) могут быть любые буквы.

Пример выходного сигнала:

Enter a string: ann bmm cmm 
Count is: 1 

Пример выходного сигнала:

Enter a string: ann bmm cmm ckc 
Count is: 3 

Answer 1

Пусть a[k] быть равно числу 'a' с индексами i<=k.
Пусть c[k] будет равно числу 'c' с индексами i>=k.
Затем для каждого k: s[k] == 'b' у нас есть решения a[k]*c[k].

Это возможная реализация (алгоритм можно упростить, например, только один массив требуется):

char* s = "pax byb zic abbc"; 
int n = strlen(s); 
int a[n], c[n]; 
a[0] = (s[0] == 'a') ? 1 : 0; 
for (int k = 1; k < n; ++k) 
    a[k] = a[k - 1] + ((s[k] == 'a') ? 1 : 0); 
c[n - 1] = (s[n - 1] == 'c') ? 1 : 0; 
for (int k = n - 2; k >= 0; --k) 
    c[k] = c[k + 1] + ((s[k] == 'c') ? 1 : 0); 
int r = 0; 
for (int k = 0; k < n; ++k) 
    if (s[k] == 'b') 
     r += a[k] * c[k]; 
printf("%d\n", r); 

Answer 2

Не эта проблема просто взывают к рекурсии:

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

int occurrences(const char *pattern, const char *string) { 
    int sum = 0; 

    size_t p_length = strlen(pattern); 

    if (p_length > 0) { 

     size_t s_length = strlen(string); 

     for (int i = 0; i < s_length; i++) { 

      if (pattern[0] == string[i]) { 
       sum += (p_length == 1) ? 1 : occurrences(pattern + 1, string + i + 1); 
      } 
     } 
    } 

    return sum; 
} 

int main(int argc, char *argv[]) { 
    printf("%d\n", occurrences(argv[1], argv[2])); 

    return 0; 
} 

ПРИМЕРЫ

> ./a.out "abc" "ann bmm cmm" 
1 
> ./a.out "abc" "ann bmm cmm ckc" 
3 
> ./a.out "abc" "pax byb zic abbc" 
8 
>