HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

isRotation and isSubstring method

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
andisrotationissubstringmethod

Problem

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 
#include 
#include  

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;
}

Solution

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++;
}

Code Snippets

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

    i++;            
}
int j = 0;
...
for(size_t i = 0; i < (2*len2); i++)
{
    ...
    j++;
}
int j = 0;
int i = 0;
while(s1[i] != '\0')
{
    if(s2[j] == s1[i])
        j++;

    i++;            
}

Context

StackExchange Code Review Q#115683, answer score: 5

Revisions (0)

No revisions yet.