Check if string is reverse substring

Question

I need to write function which will check if string s2 is reverse substring of string s1, and return 1 if the condition is true. Function should be made using pointer arithmetic.

For example:

char s1[] = "abcdef";
char s2[] = "edc";

Function would return 1 because string s1 contains reverse string s2.

#include <stdio.h>
int reverseSubstring(const char *s1, const char *s2) {
  while (*s1 != '\0') {
    const char *p = s1;
    const char *q = s2;
    while (*p++ == *q++)
      if (*q == '\0')
        return 1;
    s1++;
  }
return 0;
}

int main() {
  char s1[] = "abcdef";
  char s2[] = "edc";
  printf("%d", reverseSubstring(s1, s2));
  return 0;
}

This function does the opposite. It checks if the string is substring and in my case it returns 0. It should return 1. How to modify this to work?

Note: it is not allowed to use functions from the string.h, stdlib.h libraries, nor the sprintf and sscanf functions from the stdio.h library. It is not allowed to create auxiliary strings or strings in function or globally.

I don't see where you are reversing or searching backwards anywhere. You might want to write up the algorithm in pseudo-code first, make sure it makes sense, and then adjust your code accordingly. — siride
– siride, Commented Feb 6, 2022 at 15:15

klutt · Accepted Answer · 2022-02-08 00:05:13Z

Slight modification to parts of your code:

const char *q = s2;

while(*q) q++; // Make q point to end of string

while (*p++ == *--q) // Decrement instead of incrementing
  if (q == s2) // If we have traversed complete substring
    return 1;

This is most likely good enough for a school task, which this most likely is. But it might be good to know that the operation q-- will invoke undefined behavior for an empty string because it will make q point to the element before the string. That can be easily fixed. Just add if(*s2 == '\0') return 1; in the beginning of the function because an empty string is a substring of every string.

For completeness, here is a full version with some small fixes and optimizations. I also took the liberty of replacing a while loop with the library function strlen even if it was forbidden in the task. After all, the while loop is described above, and strlen is easy to implement on your own.

const char *
reverseSubstring(const char *s1, const char *s2) {
    if(*s2 == '\0') return s1;

    const char *end = s2 + strlen(s2);

    while (*s1 != '\0') {
        const char *p = s1;
        const char *q = end;
         
        while (*p++ == *--q)) {
            if (q == s2) return s1;
        }
          
        s1++;
    }

    return NULL;
}

Note that I changed the return type. It returns NULL if no match is found, but if a match is found, it returns a pointer to the first match. That means it contains more information for free.

Collectives™ on Stack Overflow

Check if string is reverse substring

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related