substrings

I just made a program which searches for subtrings from a char* the hard way.
does someone have an algoritm which is better than this?
here's my code...

Code:

---

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<stdio.h>
enum Bool{false, true};

Bool search(char sub[], char sup[]){
int subl=strlen(sub), supl=strlen(sup), st=0;
Bool flag = false;
if(supl<subl)return false;                  // sub larger than superstring.
else{
        for(int i=0; i<subl; i++)
        for(int j=st; j<supl && i<subl; j++)
                if(sub[i]==sup[j]){
                flag = true;
                i++;
                }else{
                flag = false;
                i=-1;
                st++;
                break;
                }
        return flag;
}
}

void main(){
clrscr();
char a[20], b[20];
do{
gets(a);
gets(b);

if( search(a, b) )cout<<"Substring !";
else cout<<"Not substring !";
cout<<"\n'q' to quit...\n\n\n";
}while( getch()!='q' );
getch();
}

---

This code is like noodles;
Even I can't make out the head or tail of it now.
P.S. I dont want to use any standard 'String' class or anything.

> does someone have an algoritm which is better than this?
Yes, but until you get past the "void main" and "gets(a)" problems, there isn't much point explaining.

Also, you really need to use the preview button - Half your code is lost in italics.

Why do you hate 'void main()' and 'gets()'?
Does someone pay you?
I use void since I'm not returning any value.
Is'nt that the standard?
And the italics might be some typo.
I copied and pasted.
And Ifound the reason for italics...
its the subscript thingi with 'i' inside.
I don't know the correction.

Main has to return due to compatibility issues. E.G so external programs can check if it exited successfully or not.

Also gets() is unsafe because it can be used to cause a buffer overflow.

Id use cin.getline()

Quote:

---

Originally Posted by arjunajay

I just made a program which searches for subtrings from a char* the hard way.

---

Really? Did you write it in C or C++?

Code:

---

C++ Code
//good ole i/o streams
cout << "Substring !";

---

Code:

---

C Code
//strange boolean enumeration
enum Bool{false, true};

---

Code:

---

Bad C++ Code
//.h headers are deprecated
//use <iostream> and the std namespace
#include<iostream.h>

---

Code:

---

Bad C Code
//use fgets
gets(a);

---

Code:

---

Just Plain Wrong Code
//use int main
void main()

---

Quote:

---

Originally Posted by arjunajay

This code is like noodles; Even I can't make out the head or tail of it now.

---

If you wrote it, surely you remember the logic of what you did. Explain to us the logic of your algorithm.

>Why do you hate 'void main()' and 'gets()'?
Because void main is wrong and gets is unsafe. Why do you like 'void main()' and 'gets()'?

>I use void since I'm not returning any value.
Yet the standard requires main to return an int value in all cases. And since 0 is returned by default if you fall of the end of main with a modern compiler, you have no excuse for using void main. The following is valid C++:

Code:

---

int main()
{
}

---

However, this is not valid C++ unless your compiler allows it as a non-portable extension:

Code:

---

void main()
{
}

---

Therefore, int main requires less typing than void main on a conforming compiler, so only stubborn and ignorant people would use void main[1].

>Is'nt that the standard?
No, and it never has been, even as far back as K&R C. main has always returned int, and the standards reflect that history.


[1] Assuming a hosted implementation. On a freestanding implementation, there are no restrictions for main because it's not bound by the runtime environment. However, if you're on a freestanding implementation, you likely wouldn't be asking us for help.

> Why do you hate 'void main()' and 'gets()'?
Because they're flat out wrong.
"Works for me" is no defence when someone shows up at your door with a buffer overflow problem caused by your sloppy coding. Either learn to do it properly, or just get out of programming.

> Does someone pay you?
Yes, I get paid quite well thanks, for being a pretty damn good programmer who doesn't make loads of rubbish mistakes which need expensive fixing later on.
If you ever want to get a job, you can be pretty sure of lots of rejections if you fail to recognise these as common programming pitfalls at the interview.

> I use void since I'm not returning any value.
It's not up to you - the environment wants a value whether you feel like returning anything or not. If you have nothing to return, then a simple
return 0;
is all you need. How hard is that?

> Is'nt that the standard?
No. void main has never been the standard, and using gets() is just plain dumb.
I can tell that you've never read the FAQ.

> And the italics might be some typo.
Yeah, unfortunately, a subscript of i matches the italics tag.
Simply putting a space in there should fix it.

Thanks for all the replies.
But I never found what I wanted... :(
and about the correction for my c++ code...
My compiler is some pre-standard thingi.
I tried to download both Borland and GCC and Microsoft C++ compilers so that i can start using standrad C++.
But I nearly fainted when the down load times showed 6 to 23 hours. My phone bill would not just skyrocket; but it will cross light speed and be thrown back in time(???).

http://www.bloodshed.net/dev/devcpp.html
How long would it take you to d/l 9MB?

Be creative - look for copies of compilers on CD's which come with magazines, find a friend with a better IP connection and a CD burner.
Or maybe there's some local tech company would be willing to help you out. If you keep in contact with them, it'll look good at job finding time.
Or the local library....

> My compiler is some pre-standard thingi.
Yeah, so it's really not the best idea to learn a bunch of outdated stuff, only to have to unlearn it again later on.

>But I never found what I wanted...

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

---

There are better string search algorithms, but this (in whatever form you care to present it) is the simplest.

Thanks for the code.
I'll figure it out.
I did'nt figure it could be this small. :)

Code:

---

const char *substr(const char *s, const char *match)
{
  do {
    const char *p, *q;
    //if both strings match it'll end up comparing chars after the string's end
    for (p = s, q = match; *p == *q && *q!=0 ; p++, q++)
      ;
    if (*q == '\0')
      return s;
  } while (++*s != '\0');//i think we want to know if the next char is valid, not the actual

  return 0;
}

---

Did I just try to fix Prelude's code ?!? :D

title.

Thanks for the correction but it gave an error at:

Code:

---

}while(++*s != '\0');

---

it was "cannot modify a constant object."
so I changed it to :

Code:

---

}while(*(++s) != '\0');

---

and it woked just fine. ;). :D
Thanks again !!!

yeap :P it's a const char, and since ++ has precendence equal to *, ++*s will try to increment *s, but *(s++) will increment the pointer. just a small error :P
http://www.cppreference.com/operator_precedence.html

>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.

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

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.

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

>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.

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!!!

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

---

Quote:

---

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.

>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. :D But I guess when you're a perfectionist, it can bug you.

>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.
;)

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

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?

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.

Quote:

---

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.

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++.

You guys are right; re-inventing the wheel will get boring. But I'm only new and I want to know what the basics of these things are. Once I do, Like you said, Re-inventing the... will get boring and I'll jump into STL.