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.

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?

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.

Well, do you need to count overlapping occurrences? For example, should findx("xx", "xxxx") print 2 or 3?

Quote:

---

Originally Posted by laserlight

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

How would you do it yourself if this were a task in real life?

Quote:

---

Originally Posted by Elysia

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?

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 Elysia

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.

Quote:

---

Originally Posted by darren78

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.

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 Elysia

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!

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?

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 Elysia

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.

Sorry first line...it should say i==2, not x==2.

I think I see your twisted sense of logic now. It's undoubtedly different from how I would do, and that is why I was a little thrown off.
I just made a little remark about the subtraction. I didn't mean it was wrong, because I wasn't sure and I didn't test.

Out of curiosity, how would you do it? I'm always interested to see how other people would tackle the same problem?

I do think the -1 was incorrect, but somehow it seemed to work? Not sure how tbh.

Patience. After I wrote the reply, I started working on my own version. And a few minutes later, here it is:

Code:

---

bool IsStrInStr(char* src, char* find, size_t length_of_src, size_t length_of_find)
{
    if (length_of_src < length_of_find)
        return false;
    for (int i = 0; i < length_of_src; ++i)
    {
        if (src[i] != find[i])
            return false;
    }
    return true;
}

size_t findx(char* src, char* find)
{
    size_t len_src = strlen(src);
    size_t len_find = strlen(find);
    int found = 0;

    for (int i = 0; i < len_src - len_find; ++i)
    {
        if (IsStrInStr(&src[i], find, len_src - i, len_find)
            found++;
    }   
   
    return found;
}

---

(Not tested.)

Quote:

---

Originally Posted by Elysia

Patience. After I wrote the reply, I started working on my own version. And a few minutes later, here it is:

Code:

---

bool IsStrInStr(char* src, char* find, size_t length_of_src, size_t length_of_find)
{
    if (length_of_src < length_of_find)
        return false;
    for (int i = 0; i < length_of_src; ++i)
    {
        if (src[i] != find[i])
            return false;
    }
    return true;
}

size_t findx(char* src, char* find)
{
    size_t len_src = strlen(src);
    size_t len_find = strlen(find);
    int found = 0;

    for (int i = 0; i < len_src - len_find; ++i)
    {
        if (IsStrInStr(&src[i], find, len_src - i, len_find)
            found++;
    }   
   
    return found;
}

---

(Not tested.)

---

Thanks. Are the size_t templates? I've not covered them yet. I'll make a note of this code and come back once I understand templates.

They aren't templates. It's the type strlen returns.
strlen (MSDN)

Quote:

---

Originally Posted by Elysia

They aren't templates. It's the type strlen returns.
strlen (MSDN)

---

Does using size_t have benefits over using, for example, int?

Is it like size_type where is it guaranteed to hold any number, whereby int would wrap around once the value gets too high?

No, all variables are finite since there's finite storage. But strlen returns a size_t. And if you use a smaller data type, you may lose data. So by using size_t, you are guaranteed not to lose any information. That's all.
Keep the type chain.
(Plus the fact that a length cannot be negative; so assigning it to an int may cause signed issues.)

Quote:

---

Originally Posted by Elysia

No, all variables are finite since there's finite storage. But strlen returns a size_t. And if you use a smaller data type, you may lose data. So by using size_t, you are guaranteed not to lose any information. That's all.
Keep the type chain.
(Plus the fact that a length cannot be negative; so assigning it to an int may cause signed issues.)

---

Okay cheers again.

theres an O(n) solution, KMP algo

Quote:

---

Originally Posted by rodrigorules

theres an O(n) solution, KMP algo

---

Excellent....thanks, will have a read up on that.