计算一个字符串在另一个字符串中出现的次数

Question

我已经花了 3 个多小时试图解决这个问题，但它并不是 100% 有效。请帮助我。

问题:创建一个接收两个字符串(A 和 B)并显示字符串 B 的单词在 A 中出现的次数的函数，而不使用属于库的任何函数。例如:

• 字符串 A:house houuse househousehous
• 字符串 B:house

需要证明单词house在字符串A中出现了3次。

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

void count_string_b_a(char *a, char *b){
   int i,j,k=0,size_a,size_b,equal=0,cont=0;
   size_a = strlen(a); 
   size_b = strlen(b);
   j=0;
   for(i = 0; i < size_b; i++){ 
     for(j = 0; j < size_a; j++){ 
        k=0;
        equal=0;
        for(k=0; k<size_b; k++){
           if(a[j+k] == b[i+k]) equal++;
           if(equal==size_b) cont++;
        } 
      } 
   }    
   printf("B %s appears %d times in A %s",b,cont,a);
}

int main(){
   int i;
   char a[40], b[10];
   scanf("%[^\n]s",&a); getchar();
   scanf("%[^\n]s",&b);
   count_string_b_a(a,b);
   getch();
 }

Answer 1

这是我对这个问题的简单的解决方案，使用我在评论中建议的两个循环:

#include <stdio.h>

static
int count_occurrences(const char *haystack, const char *needle)
{
    int count = 0;
    for (int i = 0; haystack[i] != '\0'; i++)
    {
        int j;
        for (j = 0; needle[j] != '\0' && needle[j] == haystack[i+j]; j++)
            ;
        if (needle[j] == '\0')
            count++;
    }
    return count;
}

int main(void)
{
    {
    const char haystack[] = "house houuse househousehous";
    const char needle[] = "house";

    printf("Haystack <<%s>> vs needle <<%s>> = %d\n",
           haystack+0, needle+0, count_occurrences(haystack+0, needle+0));
    printf("Haystack <<%s>> vs needle <<%s>> = %d\n",
           haystack+1, needle+1, count_occurrences(haystack+1, needle+1));
    printf("Haystack <<%s>> vs needle <<%s>> = %d\n",
           haystack+1, needle+0, count_occurrences(haystack+1, needle+0));
    printf("Haystack <<%s>> vs needle <<%s>> = %d\n",
           haystack+1, needle+2, count_occurrences(haystack+1, needle+2));
    printf("Haystack <<%s>> vs needle <<%s>> = %d\n",
           haystack+6, needle+4, count_occurrences(haystack+6, needle+4));
    }

    {
    char *haystack = "pencil pencil penciil pen penc pe pen55cil penci9llppencil55 pencillip peplic pencilrpencilpe";
    char *needle = "pencil"; 
    printf("Haystack <<%s>> vs needle <<%s>> = %d\n",
           haystack+0, needle+0, count_occurrences(haystack+0, needle+0));
    }

    return 0;
}

注意出现次数的计算是如何与出现次数的打印分开进行的。报告出现次数的函数通常很有用；同时打印数据的函数不太可能被重用。通常，将 I/O 与计算分开是个好主意。

示例输出:

Haystack <<house houuse househousehous>> vs needle <<house>> = 3
Haystack <<ouse houuse househousehous>> vs needle <<ouse>> = 3
Haystack <<ouse houuse househousehous>> vs needle <<house>> = 2
Haystack <<ouse houuse househousehous>> vs needle <<use>> = 4
Haystack <<houuse househousehous>> vs needle <<e>> = 3
Haystack <<pencil pencil penciil pen penc pe pen55cil penci9llppencil55 pencillip peplic pencilrpencilpe>> vs needle <<pencil>> = 6

存在更好的算法

上面编码的算法是天真的；有许多更好的字符串匹配算法可用(例如，Boyer-Moore、Knuth-Morris-Pratt:参见 Exact String Matching Algorithms 示例)。但是，它确实有效并且易于理解。对于示例字符串，这可能无关紧要；对于生物信息学和 DNA 片段匹配，这将非常重要。