# Did you twist my words?

### Challenge

Given two strings, determine if the second string is a rotation of the first.

### Specifications

1. The first argument is a path to a file.
2. The file contains multiple lines.
3. Each line is a test case represented by two comma separated strings.
4. For each test case print out True/False if the second string is a rotation of the first.

Sample Input

Code,deCo
Review,wRevie
testcase,casetoast

Sample Output

True
True
False

Source

My solution

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

#define LINE_LENGTH 64

char* str_mul(char* str, int times) {
char *string_multiplied = malloc(sizeof(str) * times + 1);
for (int i = 1; i <= times; i++) {
strcat(string_multiplied, str);
}
return string_multiplied;
}

bool is_rotated(char *original, char *test_case) {
int original_length = strlen(original);
char *rotation_superset = str_mul(original, 2);
bool is_substring = strstr(rotation_superset, test_case) != NULL;
return original_length == strlen(test_case) && is_substring;
}

char* parse_and_evaluate(char *line) {
const char tokens[] = ",\n\r";
char *original = strtok(line, tokens);
char *test_case = strtok(NULL, tokens);
return is_rotated(original, test_case) ? "True" : "False";
}

int main(int argc, char *args[]) {
if (argc < 2) {
fprintf(stderr, "File path not provided. Exiting...\n");
return 1;
}

if (argc > 2) {
puts("Excessive arguments, only the first will be considered.");
}

FILE *file = fopen(args[1], "r");
if (file == NULL) {
perror("Error");
return 1;
}

char line[LINE_LENGTH];
while (fgets(line, LINE_LENGTH, file)) {
printf("%s\n", parse_and_evaluate(line));
}

fclose(file);
}

## 2 Answers

You're bleeding memory for every line in the file. This is probably ok for the challenge, however it's a good idea to get into the habit of cleaning up after yourself.

The call to malloc in str_mul needs to have a corresponding free call somewhere to release the memory. Looking at your program in it's current state, the easiest way to do that is probably in the is_rotated method like so:

bool is_rotated(char *original, char *test_case) {
int original_length = strlen(original);
char *rotation_superset = str_mul(original, 2);
bool is_substring = strstr(rotation_superset, test_case) != NULL;
free(rotation_superset);
return original_length == strlen(test_case) && is_substring;
}

I'd be tempted to actually move the malloc into the same method and pass the buffer into the str_mul method so that the allocation and release are at the same level. This would also allow you to simply declare a local on the stack in is_rotated, rather than needing to use malloc:

void str_mul(char* str, char *string_multiplied, int times) {
string_multiplied[0] = '\0';
for (int i = 1; i <= times; i++) {
strcat(string_multiplied, str);
}
}

bool is_rotated(char *original, char *test_case) {
int original_length = strlen(original);
char rotation_superset[LINE_LENGTH*2];
str_mul(original, rotation_superset, 2);
bool is_substring = strstr(rotation_superset, test_case) != NULL;
return original_length == strlen(test_case) && is_substring;
}

malloc Vs calloc

malloc isn't guaranteed to return zero initialized memory. Since you're using strcat to append to the buffer, you should really ensure that the memory is a null terminated array. You can either do that by initially null terminating it (as in my example above), or by using calloc instead.

• char rotation_superset[LINE_LENGTH*2]; --> char rotation_superset[LINE_LENGTH*2 + 1]; Commented Sep 22, 2016 at 12:43
• @chux the original contains a maximum string of LINE_LENGTH - 1 (it already contains a null terminator from the fgets call). str_mul copies the string into the buffer twice, so really we need (LINE_LENGTH - 1)*2 + 1 or (LINE_LENGTH * 2) - 1, but (LINE_LENGTH*2) seemed close enough. Am I missing something? Commented Sep 22, 2016 at 13:02
• My error, thought code was char rotation_superset[original_length*2]; (a VLA). but I see this answer well uses the macro LINE_LENGTH. Part of the source of my error was OP using ...LENGTH when ....SIZE better matches. ...LENGTH with string code hints at the length of a string, not its size. Commented Sep 22, 2016 at 13:36

In addition to @forsvarir good answer:

Code is broken

str is a pointer. malloc(sizeof(str) * times + 1); allocates memory for a bunch of pointers

char* str_mul(char* str, int times) {

// bad
// char *string_multiplied = malloc(sizeof(str) * times + 1);

// Corrected
size_t len = strlen(str);
char *string_multiplied = malloc(len * times + 1);
string_multiplied[0] = '\0';  // also null character terminate

for (int i = 1; i <= times; i++) {
strcat(string_multiplied, str);
}
...

Efficiency, do string length compare test original_length == strlen(test_case) first. With mis-matched lengths, call to str_mul() not needed.