How to Check for All Inclusive in C

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 `arr``contain_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);
}
}
``````