rate my (C++) code: a recursive strstr sans any standard library string functions :)

Question

So, the idea was a write a recursive function that compares two strings to see if string 'prefix' is contained in string 'other', without using any standard string functions, and using pointer arithmetic. below is what i came up with. i think it works, but was curious - how elegant is this, scale 1-10, any obvious funky moves you would have done instead?

thanks.

bool is_prefixR(char* prefix, char* other) {
  static int prePos = 0,othPos = 0; 
  //  static int othPos = 0;
  bool test;
  test = ( *(prefix+prePos) == *(other+othPos)); //checks to see if same

  if (!*(prefix+prePos)) { return 1; } //end of recursion
  if (!*(other+othPos)) { return 0; }

  if (!test) {
    othPos++; //move othPos pointer by 1
    prePos = 0; //reset the prefix position
    return(is_prefixR(prefix, other)); //lets try again
  } else { //chars are the same
    othPos++; //move othPos pointer by 1
    prePos++;
    return(is_prefixR(prefix, other)); //lets try again
  }
    return 0;
}

Answer 1

1. This won't work correctly on all strings. For example: prefix="aab", other="aaab"

2. Don't use static variables. The function will fail the second time it's called because of them.

3. Don't use recursion: for long strings you can get a stack overflow. Use a loop instead.

4. The name "prefix" is used for a string appearing at the beginning of another - this is not the case here.

Answer 2

Maybe remove all the unecessary parens? But even then I would give it zero in the elegance stakes. The first thing an elegant function must do is to perform one task, and your description of the function - "compares two strings to see if string 'prefix' is contained in string 'other'" simply doesn't make any sense. a prefix must begin a string, not be included in it.

Answer 3

//psuedocode

if prefix == 0
   return true
else if other == 0
   return false
else return (*prefix == *other) && is_prefix(1+prefix, 1+other);

Answer 4

It is 1AM and far to late for understanding code, however such a simple function should be really easy to comprehend and your code isn't. Static variables when writing functions are not a good idea because they make it incredibly hard to debug as the function ceases to become stateless. Try passing the values you need to the next function, and if you find you can't, try writing it a different way. You also used prefix in the wrong way. I think you meant substring.

I present two functions below that do what you want and are fairly foolproof with everything except strings that are not null terminated. It is not quite as fast as it could be, as is_substr will continue to try and compare even when other is shorter than sub. You seemed to indicate elegance was the name of the game though, so I avoided all added complexity.
Note: is_substr depends on is_prefix.

bool is_prefix(const char* prefix, const char* other) {
    if ( *prefix == 0 ){
     return true;
    }else if ( *other == 0 || *prefix != *other ){
     return false;
    }
    return is_prefix(++prefix, ++other);
}

bool is_substr(const char* const sub, const char* other) {
    if ( *other == 0 ){
     return false;
    }else if ( is_prefix(sub, other) ){
     return true;
    }
    return is_substr(sub, ++other);
}

Just to give you an idea of the functions output

is_substr("aab", "aaab"); //1
is_substr("ab", "ba"); //0
is_substr("aab", "a"); //0
is_substr("a", "bab"); //1

is_prefix("a", "a"); //1
is_prefix("a", "ab"); //1
is_prefix("ab", "a"); //0
is_prefix("aab", "aaab"); //0

Answer 5

If you want to use recursion (bad idea, but let's suspend judgement for the moment), you can do it much more cleanly than that:

bool is_prefixR(char* prefix, char* other) {
  if (!*prefix) return true;
  if (*prefix != *other) return false;
  return is_PrefixR(prefix+1, other+1);
}

Answer 6

I'd say its elegance is 0 compared to size_t pos = string1.find(string2);

The standard library is there for a reason. Use it. Even if you wanted to create strstr, which is a C function and not a C++ function, you really don't need to avoid using strcmp. And even then, implementing strcmp yourself in a separate function is going to make this clearer. On top of that, your static variables make this function only work once. You're doing it wrong.

From your wording, it sounds like this may be a homework question? In which case you should add the homework tag, and say exactly what the requirements are.

Answer 7

The use of

static int prePos = 0,othPos = 0;

makes this function not thread safe. Are you sure that's what you want?

othPos will grow forever, so this function only works once, after the first time othPos won't begin with a valuie of 0.

I think if you are going to be using pointers, then you should be incrementing the pointers and passing modified pointers around rather than passing the base pointer down and having all of the work happen in the static ints.