isRotation and isSubstring method

Question

I have written an isRotation function that calls on isSubstring only once(I am allowed to call it only once). I have implemented my own version of isSubstring as well. Any advice is much welcome!

//Checks if one string is a rotation of the other
#include <stdio.h>
#include <string.h>
#include <stdbool.h> 

bool isRotation(char *, char *);
bool isSubstring(char *, char *);

int main(int argc, char **argv)
{
    if(argc == 3)
    {
        printf("%s %s a rotation of %s.\n", argv[2], isRotation(argv[1], argv[2])
            ? "is" : "is not", argv[1]);
    }
    else
    {
        fprintf(stderr, "Incorrect number of inputs\n");
        return -1;
    }

    return 0;
}

bool isRotation(char* s1, char* s2)
{
    size_t len1 = strlen(s1);
    size_t len2 = strlen(s2);

    if(len1 != len2 || len1 == 0 || len2 ==0)
        return 0;

    char s3[len2*2];

    bool secondCopy = false;
    int j = 0;

    /*copying 2*s2 into s3. If s2 is a rotation of s1,
      then s1 has to be found somewhere inside s3.*/
    for(size_t i = 0; i < (2*len2); i++)
    {
        s3[i] = s2[j];
        if(s2[j+1] == '\0' && secondCopy == false)
        {
            secondCopy = true;
            j = 0;
            continue;
        }
        j++;
    }

    s3[len2*2] = '\0';

    //pass the longer string to the first param
    return isSubstring(s3, s1);
}

bool isSubstring(char* s1, char* s2)
{
    //is s2 a substring of s1? 
    size_t len2 = strlen(s2);
    if(len2 == 0)
        return true;

    int j = 0;
    int i = 0;
    while(s1[i] != '\0')
    {
        if(s2[j] == s1[i])
            j++;

        i++;            
    }

    return j == len2;
}   

Answer 1

Better string copy

You are over-complicating your string duplication. There is an easier way to do it using memcpy. First, simply copy the string:

memcpy(s3, s2, len2);

Then, simply copy the string again (this time, with an offset):

memcpy(s3 + len2, s2, len2);

Notice how the second copy doesn't have - in the last argument. With it like this, you do not have to manually copy the null character over afterwards as it will use the null character from s2.

Note that you can not do this as easily with strcpy as this function will copy the entire string, including the null character.

---

Not true substring

Your isSubstring function doesn't actually find the substring of a string very well. Take these two strings as an example:

abec abc

Your function would return true to these if these were passed in in this order. A simple fix to this would be to reset j to 0 every time a character is encountered that is not the right one.

while(s1[i] != '\0')
{
    if(s2[j] == s1[i]) {
        j++;
    } else {
        j = 0;
    }

    i++;            
}

---

Misc

---

Returning bool

return 0;

Why are you returning a number from a bool-returning method?

---

Clear up the for loop

int j = 0;
...
for(size_t i = 0; i < (2*len2); i++)
{
    ...
    j++;
}

This is somewhat confusing. You should move the j declaration right above the for loop, and move the incrementing into the signature.

---

Refactor

The string duplication logic should be moved into an external function as to spread out the logic and make sure that every function is only doing what it needs to do and nothing else.

---

Braces

Always use them, even around single-line statements. They make your code more maintainable and less error-prone.

---

While to for loop

This:

int j = 0;
int i = 0;
while(s1[i] != '\0')
{
    if(s2[j] == s1[i])
        j++;

    i++;            
}

Can be written more cleanly as a for loop:

for(int i = 0, j = 0; s1[i] != '\0'; i++) {
    if(s2[j] == s1[i])
        j++;
}

Answer 2

char s3[len2*2];
...
s3[len2*2] = '\0';

The above declaration is incorrect. You need to allocate one more character for the null character at the end. You are adding that null character, but you are invoking undefined behavior by not having enough space in the array for that character.

/*copying 2*s2 into s3. If s2 is a rotation of s1,
  then s1 has to be found somewhere inside s3.*/
for(size_t i = 0; i < (2*len2); i++)
{
    s3[i] = s2[j];
    if(s2[j+1] == '\0' && secondCopy == false)
    {
        secondCopy = true;
        j = 0;
        continue;
    }
    j++;
}
s3[len2*2] = '\0';

That's a lot of typing for what you could easily accomplish using two calls to strcpy:

strcpy(s3, s2);
strcpy(s3+len2, s2);

int j = 0;
int i = 0;
while(s1[i] != '\0')
{
    if(s2[j] == s1[i])
        j++;
    i++;            
}
return j == len2;

This is just wrong. The standard approach for determining whether some string s2 occurs within another string s1 is to loop over the substrings of s1 that start with the first character in s2, returning true if the len2-1 characters that follow are equal to the remaining characters in s2, in order.

Answer 3

You don't really need to concatenate strings. You could just "pretend" having a longer string that is s1 concatenated twice, by adjusting the index using a simple modulo.

For example, change this:

return isSubstring(s3, s1);

To this:

return isSubstring(s2, s1);

And the main loop in isSubstring can be rewritten as:

while(i < 2 * len2)
{
    if(s2[j] == s1[i % len2])
        j++;

    i++;            
}

Notice the modulo in s1[i % len2]. That is, when i reaches the end of the string, the value goes back to 0, checking again from the beginning of the string. This is practically the same as checking the index in a longer string, but without the need for a copy.

With this change, there's no more need for s3 in isRotation, so the function can be greatly simplified:

bool isRotation(char* s1, char* s2)
{
    size_t len1 = strlen(s1);
    size_t len2 = strlen(s2);

    if (len1 != len2 || len1 == 0 || len2 == 0)
    {
        return false;
    }

    return isSubstring(s1, s2);
}

Of course, with these changes, the name of the isSubstring function became misleading, as now it is adapted to our special case, and "faking" a concatenated source string. So remember to rename to something else.

Somewhat related to this, isSubstring repeats some operations that were already done in the caller, namely:

size_t len2 = strlen(s2);
if(len2 == 0)
    return true;

The caller already knows the length of s2, so it would be good to pass that as a parameter. And we also know that len2 > 0, so that check can be omitted.

Answer 4

The same library that contains strcpy() and strlen() also contains strstr(), whose exact job is to determine if one string is contained within another.

Using the function strstr() will eliminate the function isSubString(), thereby making the code much simpler and less error-prone.