文字列内のシーケンスの出現数を数えるには？

Question

入力文字列中のシーケンス 'abc'の出現回数を数えるためのCプログラムを書く。ただし、（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]がインデックスi<=kと'a'の数に等しいとします。
c[k]は、インデックスi>=kを持つ'c'の数に等しくなるようにしてください。
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 
>