substrings

**Prelude** · 06-03-2005

>Did I just try to fix Prelude's code ?!?
I make mistakes occasionally, especially when I'm in a hurry or juggling several potential implementations at the same time to see which looks best. Your solution (for that part) would work, but I think if I hadn't just thrown out code off the top of my head, it would look more like this:

Code:

const char *substr(const char *s, const char *match)
{
  do {
    const char *p, *q;

    for (p = s, q = match; *p == *q; p++, q++) {
      if (*q == '\0')
        return s;
    }
  } while (*s++ != '\0');

  return 0;
}

>i think we want to know if the next char is valid, not the actual
What if the first character in s is '\0' and the next one is out of bounds? The inner loop will do the right thing in that case, but if you pre-increment s, the outer loop could cause a seg fault by accessing invalid memory.

**arjunajay** · 06-03-2005

Now that we are all in terms, is there any way to close this thread?

**Salem** · 06-03-2005

Threads are simply abandoned when everyone has finished what they wanted to say, and the problem is solved.
If you have a question on another topic, start a new thread.

**arjunajay** · 06-03-2005

But the problem is you guys are'nt stopping posting.
Every day I see it on the top of new posts and I can't handle the suspense

**Prelude** · 06-03-2005

>But the problem is you guys are'nt stopping posting.
Welcome to the public bulletin board system. Many threads diverge in unexpected and interesting ways (hopefully after the original question is answered). Because these tangents are often the only way to get a glimpse into the really advanced stuff, or nifty ways of looking at what might otherwise be boring, we actively encourage it.

**arjunajay** · 06-08-2005

BUG ALERT !!
Prelude,
I found a bug (or atleast I think I have) in the substring function.
This was the last one suggeted by you :

Code:

const char *substr(const char *s, const char *match){
do {
    const char *p, *q;

    for (p = s, q = match; *p == *q; p++, q++) 
      if (*q == '\0')  return s;
} while (*s++ != '\0');

  return 0;
}

BUG :
art is a substr of artist and popart, but not of xxxartxxx, ie, substr returns true if it occurs either at the begining or the end only.
and I changed it to this (don't ask me why. My 6th sense quickly sensed some thing in it.(I'm not jocking)):
till now it woks fine.

Code:

const char *substr(const char *s, const char *match){
do {
    const char *p, *q;

    for (p = s, q = match; *p == *q; p++, q++) 
      if (*(q+1) == '\0')  return s; //this line is what I changed...
} while (*s++ != '\0');
return 0;
}

and futher modified to...

Code:

int substr(const char *m, const char *s){
do {
	const char *p, *q;

	for (p = s, q = m; *p == *q; p++, q++)
	  if (*(q+1) == '\0')  return 1;
}while (*s++ != '\0');

  return 0;
}

I'm serious about the 6th sense thingi.
The moment I looked at it, my mind told me to tweak the if statement.
In fact I still don't know why it ( the fix ) works!!!

**Prelude** · 06-08-2005

I think next time I just won't bother posting to these threads. I appreciate the bug notifications and suggestions for fixes, but keep in mind that I tossed that code together in about 2 minutes. The fix for the code was devised in less than that, all while I was being bombarded with other things. Clearly I don't have the time to come up with quality answers anymore.

Just to salvage my pride, here's a more serious attempt:

Code:

#include <cstring>

char *substr ( const char *s, const char *match )
{
  if ( *match != '\0' ) {
    std::size_t len = std::strlen ( match );

    do {
      while ( *s != *match ) {
        if ( *s++ == '\0' )
          return 0;
      }
    } while ( std::strncmp ( s++, match, len ) != 0 );
  }

  return (char *)--s;
}

**ggs** · 06-08-2005

Originally Posted by Prelude

Just to salvage my pride, here's a more serious attempt:

Code:

#include <cstring>

char *substr ( const char *s, const char *match )
{
  if ( *match != '\0' ) {
    std::size_t len = std::strlen ( match );

    do {
      while ( *s != *match ) {
        if ( *s++ == '\0' )
          return 0;
      }
    } while ( std::strncmp ( s++, match, len ) != 0 );
  }

  return (char *)--s;
}

and this code returns garbage and invokes undefined behavior for most inputs if `match' points to an empty string; a possibility explicitly acknowledged by your *match != '\0' check.

**swoopy** · 06-08-2005

>but keep in mind that I tossed that code together in about 2 minutes.
Well, Prelude, your tossed together stuff is better than my multiple hour, made from scratch, slow-bake, refrigerate, add icing stuff.

But I guess when you're a perfectionist, it can bug you.

**Prelude** · 06-08-2005

>and this code returns garbage and invokes undefined behavior for
>most inputs if `match' points to an empty string
True.

>a possibility explicitly acknowledged by your *match != '\0' check.
Also true. And I still made a mistake, darn it! Bah, I seem incapable of thinking properly in terms of strstr, so I'll leave it to the rest of you and go sulk in the corner.

>But I guess when you're a perfectionist, it can bug you.

**arjunajay** · 06-09-2005

Apologising for annoying you.
I just thought it fit to inform you. That's all.

**CornedBee** · 06-09-2005

Is there a specific reason NOT to use strstr()? Or std::string::find()?

Do you need a way to find a substring or do you specifically want to know how to implement substring searches?

**arjunajay** · 06-10-2005

I wanted to know the working behind it, and I made one for myself( A piece of crap ). Then I wanted to know wheteher there is some easier or standard( like bubble sort for soting. ) way. Besides I don't like using predefined class es like String.

**pianorain** · 06-10-2005

Originally Posted by arjunajay

Besides I don't like using predefined classes like String.

I won't lie; I used to think the same way. It was nice being able to re-invent the wheel. However, after a while, I got tired of writing the "grunt" functions. That's when I really got into STL and the like. The ability to leverage that much code really moves the development of programs beyond the "bits and bytes" stage.

**CornedBee** · 06-10-2005

Re-inventing the wheel for educational purposes is nice. Doing it because you don't feel comfortable with predefined classes from well-tested and even standardized libraries is common, but in the end somewhat stupid. std::string and friends are part of the C++ standard, part of the C++ programming language. Without learning them, you won't ever be able to truthfully claim you really know C++.