3
\$\begingroup\$

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;
}   
\$\endgroup\$
6
\$\begingroup\$

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++;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Re memcpy(s3 + (len2-1), s2, len2) - This is incorrect. Suppose s2 is the null-terminated string "ab". The first memcpy copies a and b into s3[0] and s3[1]. The second call to memcpy copies a and b into s3[1] and s3[2], respectively. The correct call is memcpy(s3+len2,s2,len2). \$\endgroup\$ – David Hammen Jan 3 '16 at 1:24
  • \$\begingroup\$ Re (-1 to ignore the null character) -- This too is incorrect. The value returned by strlen does not include the terminating null character. For example, The strlen length of the string "ab\0" is 2, not 3. \$\endgroup\$ – David Hammen Jan 3 '16 at 1:27
  • \$\begingroup\$ @DavidHammen Good catch(es)! Thanks for the tip! \$\endgroup\$ – SirPython Jan 3 '16 at 1:30
  • \$\begingroup\$ @SirPython Hello, my professors(UCSD) have always advised us to not use brackets for one line commands inside loops and if statements. Is that not normal? \$\endgroup\$ – Jonathan Jan 3 '16 at 18:51
  • \$\begingroup\$ And I am a little confused on your explanation of the isSubstring method. abec and abc actually shouldn't be considered substrings should they? because "abc" is actually not found anywhere in abec in that exact same order (coherent to how DavidHammen(the other responder) corrects my isSubstring) right? \$\endgroup\$ – Jonathan Jan 3 '16 at 18:58
5
\$\begingroup\$
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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You could not use strcpy for this because strcpy copies the null character. \$\endgroup\$ – SirPython Jan 3 '16 at 0:59
  • 1
    \$\begingroup\$ @SirPython -- Sure you can. The strings passed via argv are null-terminated. I would strcpy is the better choice than is memcpy because the OP is working with C-style strings. \$\endgroup\$ – David Hammen Jan 3 '16 at 1:09
  • 4
    \$\begingroup\$ @SirPython - The second call to strcpy overwrites the null character written by the first call to strcpy. That extra copy of one character is a bit superfluous. Using memcpy would be more efficient. But I'd rather sacrifice efficiency for consistency in this case. \$\endgroup\$ – David Hammen Jan 3 '16 at 1:34
  • 2
    \$\begingroup\$ @JonathanSmit -- I don't have privileges at this part of the stackexchange network to see that your question has close votes, or even to issue a close vote. I can venture a guess: Your code doesn't work. This is not a site for debugging your code. You can submit lousy but basically working code for review, but you can't submit code that just doesn't work. As for your program, try running it with abc and bac. Your function indicates that abc is a substring of bacbac. It isn't. \$\endgroup\$ – David Hammen Jan 3 '16 at 20:03
  • 1
    \$\begingroup\$ @JonathanSmit - No, it isn't. The rotations of abc are abc, bca, and cab. On the other hand, cba, acb, and bac are not rotations of abc. \$\endgroup\$ – David Hammen Jan 3 '16 at 20:14
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why bother to edit trivia? We are not in English class, trying to get a good grade on some composition paper. \$\endgroup\$ – user3629249 Jan 4 '16 at 5:16
  • \$\begingroup\$ I was aware of the strstr() function; however, i just wanted to practice writing an isSubstring method. \$\endgroup\$ – Jonathan Jan 4 '16 at 7:34
  • 1
    \$\begingroup\$ @user3629249 No, but if a post is properly formatted and contains proper grammar, then it is nicer to read and overall improves the content of this site. It also helps with first impressions from new users. \$\endgroup\$ – SirPython Jan 5 '16 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.