c - 如何查找字符串中子字符串的所有出现次数和所有位置？

Question

我需要查找所有出现并输出字符串中子字符串的所有位置。

例如:我的字符串是 abaaab ，我的子串是 aa , 位置是 3和 4 ，因为在 aaa我的 substr 重复了两次。

我希望从右到左打印末尾的位置，在子字符串的位置之后，我想要子字符串的出现次数。

我试着这样做，我有这个:

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

int main(){
    char *str, c;
    int x = 0, y = 1;

    str = (char*)malloc(sizeof(char));

    printf("Inserisci stringa principale : ");

        while (c != '\n') {
        // read the input from keyboard standard input
        c = getc(stdin);

        // re-allocate (resize) memory for character read to be stored
        str = (char*)realloc(str, y * sizeof(char));

        // store read character by making pointer point to c
        str[x] = c;

        x++;
        y++;
        }

    str[x] = '\0'; // at the end append null character to mark end of string

    printf("\nLa stringa inserita : %s", str);

      char *sub, b;
      int w = 0, z = 1;

      sub = (char*)malloc(sizeof(char));

      printf("Immetti sottostringa da cercare : ");

          while (b != '\n') {
            // read the input from keyboard standard input
            b = getc(stdin);

            // re-allocate (resize) memory for character read to be stored
            sub = (char*)realloc(sub, z * sizeof(char));

            // store read character by making pointer point to c
            sub[w] = b;

            w++;
            z++;
          }

      sub[w] = '\0'; // at the end append null character to mark end of string

    char *p1, *p2, *p3;
    int i=0,j=0,flag=0;

      p1 = str;
      p2 = sub;

      for(i = 0; i<strlen(str); i++)
      {
        if(*p1 == *p2)
          {
              p3 = p1;
              for(j = 0;j<strlen(sub);j++)
              {
                if(*p3 == *p2)
                {
                  p3++;p2++;
                } 
                else
                  break;
              }
              p2 = sub;
              if(j == strlen(sub))
              {
                 flag = 1;
                printf("\nSottostringa trovata all'indice : %d\n",i);
              }
          }
        p1++; 
      }
      if(flag==0)
      {
           printf("Sottostringa non trovata");
      }
    free(str);
    free(sub);
    return (0);
    }

但它只显示第一次出现的位置，而不是出现次数。

Answer 1

您的代码中有多个问题:

您的字符串重新分配方案不正确:分配的空间对于字符串来说太短了一个字节，并且您从未测试过内存分配失败。您可以使用 getline()如果您的系统支持它或至少编写一个函数来分解代码。

c第一次循环测试时未初始化 c != '\n' : 这有未定义的行为。

您的匹配算法太复杂:您同时使用索引值和移动指针。使用其中之一。

这是一个简化版本:

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

/* read an allocated string from stream.
   stop at newline, not included in string.
   Return NULL upon EOF
 */
char *my_getline(FILE *stream) {
    char *line = NULL;
    size_t pos = 0;
    int c;

    while ((c = getc(stream)) != EOF) {
        char *newp = realloc(line, pos + 2);
        if (newp == NULL) {
            free(line);
            return NULL;
        }
        line = newp;
        if (c == '\n')
            break;
        line[pos++] = (char)c;
    }
    if (line) {
        line[pos] = '\0';
    }
    return line;
}

int main(void) {
    char *str, *sub;
    size_t len1, len2, i, count = 0;

    // type the main string
    printf("Inserisci stringa principale :\n");
    str = my_getline(stdin);

    // type the substring to search for
    printf("Immetti sottostringa da cercare :\n");
    sub = my_getline(stdin);

    if (str && sub) {
        len1 = strlen(str);
        len2 = strlen(sub);
        for (i = 0; i + len2 <= len1; i++) {
            if (!memcmp(str + i, sub, len2)) {
                count++;
                // substring found at offset
                printf("Sottostringa trovata all'indice : %zu\n", i);
            }
        }
        if (count == 0) {
            // substring not found
            printf("Sottostringa non trovata\n");
        }
    }
    free(str);
    free(sub);
    return 0;
}

笔记:

上面的代码在搜索字符串的每个偏移处查找空子字符串的匹配项。是否应该找到匹配项是规范问题，但这种行为与 strstr() 的行为一致。 .

您也可以使用标准功能 strstr()找到匹配项。

这是使用 strstr() 的主循环版本:

if (str && sub) {
    for (char *p = str; (p = strstr(p, sub)) != NULL; p++) {
        count++;
        // substring found at offset
        printf("Sottostringa trovata all'indice : %tu\n", p - str);
        if (*p == '\0')  /* special case for the empty string */
            break;
    }
    if (count == 0) {
        // substring not found
        printf("Sottostringa non trovata\n");
    }
}