-2
\$\begingroup\$

I have written a C function that finds the shortest substring that can be repeated to produce the entire string.

  • input: abcdeabcde
    result: abcde

  • input: abababab
    result: ab

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

int
getr_seq(char *arr, int n, int mid, char *array, int length)
{
  int temp = mid;
  int i = 0;
  int length1 = 0;
  while (i < n)
    {
      if (arr[i] == arr[mid])
        {
          if (i < temp)
            {
              array[length] = arr[i];
              length++;
            }
          length1++;
        }

      i++;
      mid++;

      if (i == n)
        {
          if ((length1 + length) != i)
            {
              return 0;
            }

          return length;
        }
    }
}

int
func1(char *arr, int n, char *array, int *ret)
{
  for (int i = 1; i < n; i++)
    {
      if (n % i == 0)
        {
          int mid = n / i;
          *ret = getr_seq(arr, n, mid, array, 0);
          if (*ret > 0)
            {
              for (int j = 0; j < *ret; j++)
                ;
              return *ret;
            }
        }
    }
}

void
main()
{
  char arr[10] = "abcdeabcde";
  int n = strlen(arr) - 1;
  char array[n];
  int ret = 0;

  func1((char *)&arr, n, (char *)&array, &ret);
  printf("(");
  for (int x = 0; x < ret; x++)
    {
      printf("%c", array[x]);
    }
  printf(")");
}
\$\endgroup\$
9
  • 3
    \$\begingroup\$ As long as nobody has written an answer yet, you are free to modify your code, to better prepare it for a review by humans. Please run a code formatter over your code since in its current inconsistent form it is barely readable for experienced programmers. (Or at least it's not fun to read it.) \$\endgroup\$ Jul 3, 2021 at 9:08
  • 1
    \$\begingroup\$ Also, please explain your implementation logic for func1 and getr_seq. \$\endgroup\$
    – kiner_shah
    Jul 3, 2021 at 10:24
  • \$\begingroup\$ The code isn't working. \$\endgroup\$ Jul 3, 2021 at 10:52
  • \$\begingroup\$ @PavloSlavynskyy what input did u specified. I checked again thoroughly nothing wrong \$\endgroup\$
    – user786
    Jul 3, 2021 at 11:00
  • 1
    \$\begingroup\$ This line in the code char arr[10] = "abcdeabcde"; can cause undefined behavior. The array arr is not long enough to hold the string since the string is 10 characters and C adds the '\0' to the end of the string to terminate it. You don't need to supply the string size of 10, use char arr[] = "abcdeabcde"; instead. The code does not work as written. \$\endgroup\$
    – pacmaninbw
    Jul 3, 2021 at 12:00

1 Answer 1

3
\$\begingroup\$

main()

void
main()

Oops: that's not a standard signature for main(). You probably meant int main(void).


We have a memory access bug here, that's illuminated when we run under Valgrind:

  char arr[10] = "abcdeabcde";
  int n = strlen(arr) - 1;

arr doesn't have a terminating null. It's better to use an array of unspecified size, so we can be sure that the content is actually a string:

  char arr[] = "abcdeabcde";  /* sizeof arr == 11 */

Arrays decay to pointers when passed as function arguments, so these two casts are superfluous:

   func1((char *)&arr, n, (char *)&array, &ret);

We can just write

    func1(arr, n, array, &ret);

There's no need for char-by-char printing here (and putc() would be simpler if there were):

printf("(");
for (int x = 0; x < ret; x++)
    {
        printf("%c", array[x]);
    }
printf(")");

Just use %s, and specify the field width to truncate it:

printf("(%.*s)\n", ret, array);

func1()

That's a poor name for a function. And the arguments are insufficiently clear, too. Why do we copy the return value into a pointer parameter? There's no need to do that.

We shouldn't be modifying the contents of array, so we should pass it as a const char*.

Since we're working with strings, we should accept and return size_t for number of characters.

Why are we required to pass the length of input string? The function ought to be able to determine that.

Why do we have an empty loop here?

          for (int j = 0; j < *ret; j++)
            ;

There's no return statement if the loop completes.


getr_seq()

Why are we working through this character by character, when we have a perfectly good string library provided in C? We can use strcmp() or memcmp() to compare the substrings, and strcpy()/memcpy() to copy characters (though I don't see any need to do so, meaning we can eliminate the array parameter).

This function is also missing a return statement in at least one path.


Modified code

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

static bool is_repeating(const char *arr, size_t chunk_size)
{
    /* are all substrings of length i equal? */
    for (const char *chunk = arr + chunk_size;  *chunk;  chunk += chunk_size) {
        if (memcmp(arr, chunk, chunk_size)) {
            /* no, unequal */
            return false;
        }
    }
    /* all length-i substrings identical */
    return true;
}


size_t minimal_repeating_length(const char *arr)
{
    const size_t n = strlen(arr);
    for (size_t i = 1;  i < n;  ++i) {
        if (n % i == 0 && is_repeating(arr, i)) {
            return i;
        }
    }
    return n;                   /* no repetitions, so it's the whole string */
}

int main(void)
{
    const char *arr = "abcdeabcde";

    size_t repeat_len = minimal_repeating_length(arr);
    printf("(%.*s)\n", (int)repeat_len, arr);
}

Alternative interface

Instead of returning the minimal length that repeats to form the string, we could return the substring itself, by returning a pointer to the last chunk:

/*
 * Return the shortest substring which can be repeated to create arr
 * N.B. return value is a view into arr, so has same lifetime.
 */
const char *minimal_repeating_string(const char *arr)
{
    const size_t n = strlen(arr);
    for (size_t i = 1;  i < n;  ++i) {
        if (n % i == 0 && is_repeating(arr, i)) {
            return arr + n - i;
        }
    }
    /* no repetitions, so it's the whole string */
    return arr;
}

This makes life easier for the caller (who can still use strlen() to get the length if that's needed):

int main(void)
{
    printf("(%s)\n", minimal_repeating_string("abcdeabcde"));
}
\$\endgroup\$
2
  • \$\begingroup\$ can u please add few words why u added stdbool.h . why its needed in the code? ur code included it as header file \$\endgroup\$
    – user786
    Jul 4, 2021 at 6:39
  • \$\begingroup\$ Does that need explaining? It's because I changed the helper function to return a boolean value. \$\endgroup\$ Jul 4, 2021 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.