The challenge

Input:

  • a string strng
  • an array of strings arr

Output of function contain_all_rots(strng, arr) (or containAllRots or contain-all-rots):

  • a boolean true if all rotations of strng are included in arr
  • false otherwise

Examples:

contain_all_rots(
  "bsjq", ["bsjq", "qbsj", "sjqb", "twZNsslC", "jqbs"]) -> true

contain_all_rots(
  "Ajylvpy", ["Ajylvpy", "ylvpyAj", "jylvpyA", "lvpyAjy", "pyAjylv", "vpyAjyl", "ipywee"]) -> false)

Note:

Though not correct in a mathematical sense

  • we will consider that there are no rotations of strng == ""
  • and for any array arrcontain_all_rots("", arr) --> true

The solution in C

Option 1:

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

int containAllRots(char* strng, char* arr[], int sz)
{
  int i, j, pos, rot_num = 0;
  int strng_len = strlen(strng);
  char *strng_rot = strdup(strng);
  
  // for all rotations
  for (i = 0; i < strng_len; i++)
  {
    // get current rotation
    for (j = 0, pos = i; j < strng_len; j++, pos++)
      strng_rot[j] = strng[pos % strng_len];
    
    // find rotation in array
    for (j = 0; j < sz; j++)
      if ((strcmp(strng_rot, arr[j]) == 0) && rot_num++)
       break;
  }

  free(strng_rot);
  return rot_num >= strng_len;
}

Option 2:

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

// sz is size of arr
int containAllRots(char* strng, char* arr[], int sz) {
  int length = strlen(strng);
  int i, j, k;
  int offset;
  int result = 0;
  char tempstr[length+1];
  int count=0;
  
  if (strng == "") return 1;
  
  for (k = 0; k < length; k ++) {
      for (i = 0; i < length; i++) {
          offset = ((i+k+1)%(length));
          tempstr[i] = strng[offset];
      }
      tempstr[length]='\000';
      for (j = 0; j < sz; j ++) {
          if (strcmp (tempstr, arr[j]) == 0) count ++;
      }
      if(count>=length) result = 1;
  }
  return result;
}

Option 3:

#include <stdbool.h>

int containAllRots(const char* str, const char* arr[], int sz) 
{
  for (int i = 0, len = strlen(str); i < len; i++)
  {
    char s[len], f = 0;
    memcpy(s, str + i, len - i), memcpy(s + len - i, str, i), s[len] = '\0'; // rotate    
    for (int j = 0; !f && j < sz; j++) f = !strcmp(s, arr[j]);
    if (!f) return 0;
  } 
  return 1;
}

Test cases to validate our solution

#include <stdbool.h>
#include <criterion/criterion.h>

extern void dotest(const char *string, int len, const char *const array[len], bool expected);

Test(containAllRots, SampleTests)
{
    {
        const char* s = "bsjq";
        const char* v1[5] = {"bsjq", "qbsj", "sjqb", "twZNsslC", "jqbs"};
        dotest(s, 5, v1, true);
    }
    {
        const char* s = "XjYABhR";
        const char* v1[8] = {"TzYxlgfnhf", "yqVAuoLjMLy", "BhRXjYA", "YABhRXj", "hRXjYAB", "jYABhRX", "XjYABhR", "ABhRXjY"};
        dotest(s, 8, v1, false);
    }
    {
        const char* s1 = "sObPfw";
        const char* v1[8] = {"ObPfws", "Cofuhqrmmzq", "wFvfcqU", "sObPfw", "bPfwsO", "PfwsOb", "wsObPf", "fwsObP"};
        dotest(s1, 8, v1, true);
    }
}