Thread: Occurences of a string in another string.

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    329

    Occurences of a string in another string.

    Okay, so i've written the function and it seems to work. The outline was to write a function with this signature: char* findx(char*s, char*x), that finds multiple occurences of string s in x.

    My code is:

    Code:
    char* findx(char* s, char* x)
    {
    	
    	int lens = strlen(s);
    	int lenx = strlen(x);
    	int count = 0; 
    	int found = 0;
    
    	for(int i = 0; i < lenx; ++i) {
    		for(int j = count; j < lens; ++j) {
    			if(s[j] == x[i]) {
    				++ count;
    				break;
    			}
    			count = 0;
    		}
    		if(count == lens){
    			++found;
    			count = 0;
    		}
    	}
    
    		
    cout << found;
    
    	return s;
    }
    As I said, this seems to work fine. Can anybody see anything wrong with it?

    Thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    How does a single char* return result result in multiple values?

    > Can anybody see anything wrong with it?
    How many tests have you done?
    Can you show us?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    That's where I cheated slightly. I wasn't sure from the exercise description what should be returned, so I just call the function as such:

    findx("dog", "jklkjfdogjkjkldogjkjkldog");

    That then prints out that dog has been found three times.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, do you need to count overlapping occurrences? For example, should findx("xx", "xxxx") print 2 or 3?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by laserlight View Post
    Well, do you need to count overlapping occurrences? For example, should findx("xx", "xxxx") print 2 or 3?
    Ha.....Well that looks a little bit more difficult.

    Remember.....babysteps!!

    Out of curiosity, how would I go about implementing something like that in Pseudocode, so that I can have a go proper.

    Thanks

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    How would you do it yourself if this were a task in real life?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by Elysia View Post
    How would you do it yourself if this were a task in real life?
    I would probably ask on here....

    Seriously, if i need to find stringa in stringb, would I simply start from stringb[0] and see if string a begins there and check along stringb for strlen(stringa), and then increment stringb index each time and check again from there?

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It sounds like you have a strategy for doing it already. Can't say if it's meant to check for overlapping or not.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by Elysia View Post
    It sounds like you have a strategy for doing it already. Can't say if it's meant to check for overlapping or not.
    I think it will work. Will try it this evening and post the solution.

  10. #10
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by darren78 View Post
    I think it will work. Will try it this evening and post the solution.
    Isn't it great when you figure something out!!!

    It was a very simple change in the end:
    Code:
    char* findx(char* s, char* x)
    {
    	
    	int lens = strlen(s);
    	int lenx = strlen(x);
    	int count = 0; 
    	int found = 0;
    
    	for(int i = 0; i < lenx; ++i) {
    		for(int j = count; j < lens; ++j) {
    			if(s[j] == x[i]) {
    				++ count;
    				break;
    			}
    			count = 0;
    		}
    		if(count == lens){
    			++found;
    			count = 0;
    			i = i-(lens-1); // only part I changed!
    		}
    	}
    
    		
    cout << found;
    
    	return s;
    }
    It seems to work fine with the test data I used. I inputted various lengths of 'x' strings and it was correct on each occasion!

    Anybody any suggestions to make it more efficient or is this fine as it is?

    Thanks.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Hmmm? Are you sure that's right? You are subtracting the length of the string s - 1 to i. That means i will < 0.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by Elysia View Post
    Hmmm? Are you sure that's right? You are subtracting the length of the string s - 1 to i. That means i will < 0.
    Damn. You're right. I am getting the expected output though. Let me have another play around with it!

  13. #13
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Code:
    char* findx(char* s, char* x)
    {
    	
    	int lens = strlen(s);
    	int lenx = strlen(x);
    	int count = 0; 
    	int found = 0;
    
    	for(int i = 0; i < lenx; ++i) {
    		for(int j = count; j < lens; ++j) {
    			if(s[j] == x[i]) {
    				++ count;
    				break;
    			}
    			count = 0;
    		}
    		if(count == lens){
    			++found;
    			count = 0;
    			i = i-lens+1; // only part I changed!
    		}
    	}
    
    		
    cout << found;
    
    	return s;
    }
    Okay, changed slightly. Maintains that i is positive, and it works okay I think. No idea why the previous one still worked though?

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    What is i = i-lens+1 supposed to do, though? Subtracting the length of a string from your current position in the other string makes no sense.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by Elysia View Post
    What is i = i-lens+1 supposed to do, though? Subtracting the length of a string from your current position in the other string makes no sense.

    Say for example i want to find how many occurences of 'xxx' there are in 'xxxxx', including overlapping.

    So on the first run through:

    01234
    xxxxx

    When found, ie when count == lens..i== 2. I then want it to search again from when [i] was one ahead from the beginning of the previous found 'xxx'. So on this occasion [i] = 2. Using my code i = i-lens+1, i will equal 0, however because the for loop will increment [i] also, the search will start again from [i] = 1.

    Hope this makes sense, I don't seem to be very good at explaining myself

    Edited: first line should say i==2, not x==2 as previously typed.
    Last edited by darren78; 07-27-2010 at 01:15 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please check my C++
    By csonx_p in forum C++ Programming
    Replies: 263
    Last Post: 07-24-2008, 09:20 AM
  2. Replies: 4
    Last Post: 03-03-2006, 02:11 AM
  3. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  4. creating class, and linking files
    By JCK in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2002, 02:45 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM