CODEWITHSUNDEEP
cstringsubstring
sharmila narayanan
sharmila narayanan

Reputation: 57

Rotated strings

Write code to check if s2 is rotation of s1 using only one call to isSubString (ie. waterbottle is a rotation of erbottlewat).

I write program for this but i can't able to get the desired output. Please guide me where I am going wrong.

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

int isRotated(char *s1, char *s2);
int isSubstring(char *s1, char *s2);

int isRotated(char *s1, char *s2)
{
        int r;
        char s[100];
        if(strlen(s1) == strlen(s2))
                strcpy(s, s1);
        r = isSubstring(s, s2);
        strcat(s, s1);
        return r;
}

int isSubstring(char *s1, char *s2){
        if(strstr(s1, s2))
                return 1;   
        else    
                return 0;
}

int main(void) {
        char s1[100], s2[100];
        printf("Enter the first String\n");
        scanf("%s", s1);
        printf("Enter the second String\n");
        scanf("%s", s2);

        if(isRotated(s1, s2)==1)
                printf("%s and %s are rotated string\n", s1, s2);
        else
                printf("%s and %s are not rotated string\n", s1, s2);

        return 0;
}

Upvotes: 2

Views: 375

Answers (3)

nalzok
nalzok

Reputation: 16107

To check if s2 is rotation of s1, you may want to concentrate two s1s, and try finding s2 in the new string.

It is necessary to check the length of s1 and s2. For example, s1 is "ABCD", s2 is "CDA". Then s is "ABCDABCD". strstr(s, s2) == 1, but obviously, s2 isn't rotation of s1.

Also, I'd want to call strcmp() first, because I consider a "ABCD" as rotation of "ABCD" itself. However, this is only a matter of definition.

int isRotated(char *s1, char *s2)
{
        char s[199];
        if(strlen(s1) != strlen(s2))
                return 0;
        else if(strcmp(s1, s2) == 0)
                return 1;
        else
                strcpy(s, s1);
        strcat(s, s1);
        return isSubString(s, s2);
}

BTW: "substring" is one word, so it might be better changing isSubString() to isSubstring()

Upvotes: 4

unwind
unwind

Reputation: 399863

How about this, using the concatenate-and-look-for-substring approach:

int isRotated(const char *s1, const char *s2)
{
  const size_t l1 = strlen(s1);
  const size_t l2 = strlen(s2);
  if(l1 != l2)
    return 0;
  char joined[2 * l1 + 1];
  memcpy(joined, s1, l1);
  memcpy(joined + l1, s1, l1);
  joined[2 * l1] = '\0';
  return strstr(joined, s2) != NULL;
}

Basically uses more const, variable-length array to handle varying lengths, and memcpy() when we know the length we're copying.

Upvotes: 0

Frodo
Frodo

Reputation: 749

If you do the comparison with strstr() you are searching a substring in the rotated string. So what you are doing is to find for example the string s1 ABCD in an other string s2 CDAB. So in fact s2 has no substring s1 in it and your function int isSubString(char *s1,char *s2) will always return false.

A simple solution for this would be not to compare s1 with s2 directly. You have to compare s2 to a doubled copy of s1: CDABCDAC, there you can see that this string contains a substring ABCD and your function will return true.

This would mean for your function:

int isRotated(char *s1,char *s2)
{
    char s[200];
    strcpy(s,s1); // Copy content of s1 to s
    strcat(s,s1); // Append s again with the content of s1

    if(strstr(s,s2))
       return 1;
    else
       return 0;
}

Upvotes: 3

Related Questions