Back to General and Gameplay Programming

string questions: how to count the number of instances of a string in another?

General and Gameplay Programming Programming

Started by baker March 06, 2006 09:55 AM

17 comments, last by JohnBolton 18 years, 1 month ago

1,151

March 06, 2006 12:08 PM

Quote:Original post by baker
hey drevil question: i am trying to understand the function in my head. is this sort of right?

Yea, you got it.

Out of laziness I only incremented the current position by 1. Optimally you'd probably want to increment by the string length as raz0r did. If you didn't increment at all the loop would go on forever because it would keep finding the string in the same spot. Also don't forget the error checking for empty string, as raz0r also showed.

delta user: What are you talking about? Our solutions work fine on that, returning 1, unless I misunderstood your post.

Omni-Bot: My game/mod independant AI bot framework.

raz0r

586

March 06, 2006 12:14 PM

Quote:Original post by DrEvil
delta user: What are you talking about? Our solutions work fine on that, returning 1, unless I misunderstood your post.

I think so too?

"is this hellhellhellhellhello or is it"
..................hellhellhello

delta user

164

March 06, 2006 01:10 PM

i m sorry. my mistake.
i thought you would jump to far in the string after a mismatch.

i was reading the code of drEvil.
he has commented his code with "should probably ++ this by the st2.length"

and it wouldnt find my line of text that way because it skips a part of the code

just think about it.

Someone who uses a, euhm..., delta!?

Anonymous

March 06, 2006 01:33 PM

basic_string::find
size_type find(E c, size_type pos = 0) const;
size_type find(const E *s, size_type pos = 0) const;
size_type find(const E *s, size_type pos, size_type n) const;
size_type find(const basic_string& str, size_type pos = 0) const;
Each member function finds the first (lowest beginning position) subsequence in the controlled sequence, beginning on or after position pos, that matches the operand sequence specified by the remaining operands. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

What is so hard about RTFM????

baker

158

Author

March 06, 2006 02:14 PM

im slow in the head. sorry. thanks everyone for the help.

Quote:Original post by Anonymous Poster
basic_string::find
size_type find(E c, size_type pos = 0) const;
size_type find(const E *s, size_type pos = 0) const;
size_type find(const E *s, size_type pos, size_type n) const;
size_type find(const basic_string& str, size_type pos = 0) const;
Each member function finds the first (lowest beginning position) subsequence in the controlled sequence, beginning on or after position pos, that matches the operand sequence specified by the remaining operands. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

What is so hard about RTFM????

raz0r

586

March 06, 2006 02:18 PM

Quote:Original post by delta user
i m sorry. my mistake.
i thought you would jump to far in the string after a mismatch.

i was reading the code of drEvil.
he has commented his code with "should probably ++ this by the st2.length"

and it wouldnt find my line of text that way because it skips a part of the code

just think about it.

What?
Evil's method will still return the right answer. Since he increments the search position by one, the current word will be invalid in the next pass.

"Hello this is a test" -> found "Hello".
"ello this is a test" -> no match for "Hello".

I'm probably misunderstanding you, but whatever...

[Edited by - raz0r on March 6, 2006 2:18:33 PM]

nicksterdomus

270

March 06, 2006 07:55 PM

delta user, I think the problem you are talking about would have to be a problem internal to the string.find() function. DrEvil's code has nothing in it about checking individual characters. It searchs for a whole string, it does not check against characters. I also think that you are misrepresenting the way string.find() works. While I don't know the details of the implementation of the function, I can assure you that it doesn't search in the way your diagram illustrates, it would have to backtrack. And the reason is because it doesn't work, like you said.

I tested his function on your strings, it does work, even with incrementing by the whole string.

His function does this:

starting from index 0: 012345678        "hellhellhello""hellhellhellhellhello or is it"find returns index 8increments indexincrements countstarts from index 9 this time:"hellhellhello""ellhellhello or is it"find returns no match, end whilereturn count of 1

Thetan

100

March 06, 2006 08:15 PM

this works just fine for me

#include <stdio.h>#include <unistd.h>#include <string.h>unsigned int strcount(char *h, char *n){	unsigned int c, l = strlen(n);		for (c = 0; h = strstr(h, n); ++c) h += l;		return c;}int main(int argc, char **argv){	char *test = "in the bay we get hyphy stupid dumb and hyphy\n";		printf("%s", test);	printf("e: %d\n", strcount(test, "e"));	printf("hyphy: %d\n", strcount(test, "hyphy"));	printf("z: %d\n", strcount(test, "z"));}

it outputs

Quote:
[r3d@localhost functions]$ ./strcount
in the bay we get hyphy stupid dumb and hyphy
e: 3
hyphy: 2
z: 0
[r3d@localhost functions]$

_____________________#define ever (;;)for ever delete (void *) rand();

JohnBolton

1,373

March 07, 2006 02:14 PM

Take a look at this page: EXACT STRING MATCHING ALGORITHMS

Boyer-Moore is generally the most efficient (and I assume is what is described above).

John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!

string questions: how to count the number of instances of a string in another?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

string questions: how to count the number of instances of a string in another?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines