algorithm not working like i want it to

This is a discussion on algorithm not working like i want it to within the C++ Programming forums, part of the General Programming Boards category; Im crap at C++. Could someone tell me why this wont work? I checked it over and over and I ...

  1. #1
    Back after 2 years Panopticon's Avatar
    Join Date
    Dec 2002
    Posts
    262

    Question algorithm not working like i want it to

    Im crap at C++. Could someone tell me why this wont work? I checked it over and over and I still can't see the thing I did wrong. It compiles flawlessly, and does everything like I want it to but one feature.
    Code:
    #include <iostream>
    #include <cstring>
    using namespace std;
    int search(char *str,char *sub);
    int main() {
    start:
    	int i;
    	char str[100],sub[100],exit;
    	cout<<"Input data."<<endl;
    	gets(str);
    	cout<<"Input search."<<endl;
    	gets(sub);
    	i=search(str,sub);
    	if(i) cout<<"Match found, starting from the "<<i<<"th letter of your input."<<endl;
    	else cout<<"No match found."<<endl;
    	cout<<"Repeat? y/n"<<endl;
    	do {
    		cin>>exit;
    		if(exit=='y') goto start;
    	} while(exit!='n');
    	return 0;
    }
    int search(char *str,char *sub) {
    	int len=strlen(str),i;
    	char *a,*b;
    	for(i=0;i<len;i++) {
    		a=&str[i];
    		b=&sub[i];
    		while(*a==*b) {
    			a++;
    			b++;
    		}
    		if(!*b) return i+1;
    	}
    	return 0;
    }
    (search() is suppose to tell you whether a substring match exists or not) I want the returned 'int i' to provide information on where the match starts. i.e A successful run would be something like:

    Input data.
    ifureadthisthenurgay
    Input search.
    read
    Match found, starting from the 4th letter of your input.
    Repeat? y/n

    But when I entered that exact data it gives me

    Input data.
    ifureadthisthenurgay
    Input search.
    read
    Match found, starting from the 5th letter of your input.
    Repeat? y/n

    Thanx in advance
    I AM WINNER!!!1!111oneoneomne

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,643
    It should return 4 using gets() [unless gets() retrieved the newline from the input, in which case it would return 5], but it would be wrong anyway. What is happening is "i" moves through BOTH strings, when you really want it to just move through the "str".

    So the idea is to start b back at sub[0] every run. But be sure to check "a" for null while looping, because *a == *b will be true when they both reach their null terminators, and the pointers will just happily fly through unowned memory...


    Code:
    int search(char *str,char *sub) {
    	int len=strlen(str),i;
    	char *a,*b;
    	for(i=0;i<len;i++) {
    		a=&str[ i ];
    		b=&sub[ 0 ];
    		while(*a && *a==*b) {
    			a++;
    			b++;
    		}
    		if(!*b) return i+1;
    	}
    	return 0;
    }

    Still, I would complain that first of all, strlen is just double work, it just loops through a string till it reaches a null anyway, so you can discard it completely. Finally, since pointers calculate indexes just as well as a counter, you can replace "i" too.

    Code:
    int search(char *str,char *sub) 
    {
    char *a, *b, *c;
    
        for(a = str; *a; a++) 
      {
        c = a;
        b = sub;
                                     
            while(*a && *a==*b) 
          {
            a++;
            b++;
          }
            if(!*b) 
              return (int)(c - str)+1;
      }
     return 0;
    }
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  3. #3
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Ahhh! What's that goto doing in there?! You really don't need it.
    Code:
    do
    {
    //stuff
    cout << "Enter 'y' to continue: ";
    cin >> exit;
    }while(exit == 'y');
    See, no reason to use that dreaded goto.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  4. #4
    Back after 2 years Panopticon's Avatar
    Join Date
    Dec 2002
    Posts
    262
    Hey thanx for your version of the function, it helped alot in locating the problem.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Max/min function not working correctly
    By En-Motion in forum C++ Programming
    Replies: 6
    Last Post: 03-19-2009, 12:28 AM
  2. Working with bits and SHA-1
    By Desolation in forum C++ Programming
    Replies: 6
    Last Post: 12-28-2008, 12:34 AM
  3. Second Chance Algorithm
    By Aga^^ in forum C++ Programming
    Replies: 4
    Last Post: 12-23-2008, 07:03 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21