如何統計字符串中序列的出現次數？

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]等於指數爲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 
>