Find repeating pattern in a string

Question

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(")");
}

Answer 1

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