How to find all occurrences and all position of a substring in a string?

Question

I need to find all occurrences and output all positions of a substring in a string.

For example: my string is abaaab, my substring is aa, position is 3 and 4, because in aaa my substr is repeated twice.

I want the position at the end to be printed from right to left, and after the position of substring I want the number of occurrences of my subtring.

I tried to do it and I have this:

#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);
    }

But it only shows me the position of the first occurrence, and not the number of occurrences.

Answer 1

There are multiple problems in your code:

• Your string reallocation scheme is incorrect: the space allocated is one byte too short for the string and you never test for memory allocation failure. You could use getline() if your system supports it or at least write a function to factorize the code.

• c is unsinitialized the first time you loop test c != '\n': this has undefined behavior.

• Your matching algorithm is too complicated: you use both index values and moving pointers. Use one or the other.

Here is a simplified version:

#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;
}

Notes:

• The above code finds matches for the empty substring at every offset in the search string. Whether matches should be found or not is a question of specification, but this behavior is consistent with that of strstr().

• you could also use standard function strstr() to locate the matches.

Here is a version of the main loop using 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");
    }
}