Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Pattern match question (http://www.velocityreviews.com/forums/t285175-pattern-match-question.html)

 BCC 08-23-2004 06:11 PM

Pattern match question

What is the best way to find out how many times a pattern is matched in a
string? For example if I have:

std::string s = "AAAAABBAAAABBAAAABAAABB";

I want to know how many "BB" patterns there are... is there a function that
exists to do this already or do I need to roll my own?

Thanks,
B

 Victor Bazarov 08-23-2004 06:31 PM

Re: Pattern match question

BCC wrote:
> What is the best way to find out how many times a pattern is matched in a
> string? For example if I have:
>
> std::string s = "AAAAABBAAAABBAAAABAAABB";
>
> I want to know how many "BB" patterns there are... is there a function that
> exists to do this already or do I need to roll my own?

You could write a [simple enough] predicate for 'count_if', given that
"BBB" has two 'BB' patterns, or you need to roll your own if "BBB" should
only have one.

V

 Dave 08-23-2004 07:55 PM

Re: Pattern match question

Pattern matching is done with something called regular language recognition.

If you're not familiar with this, read up on "deterministic finite
automata". By implementing a little state machine, you could do what you
want.

"BCC" <bryan@akanta.com> wrote in message
news:ZqqWc.11290\$fO.4989@newssvr29.news.prodigy.co m...
> What is the best way to find out how many times a pattern is matched in a
> string? For example if I have:
>
> std::string s = "AAAAABBAAAABBAAAABAAABB";
>
> I want to know how many "BB" patterns there are... is there a function

that
> exists to do this already or do I need to roll my own?
>
> Thanks,
> B
>
>

 Dave 08-23-2004 08:01 PM

Re: Pattern match question

"BCC" <bryan@akanta.com> wrote in message
news:ZqqWc.11290\$fO.4989@newssvr29.news.prodigy.co m...
> What is the best way to find out how many times a pattern is matched in a
> string? For example if I have:
>
> std::string s = "AAAAABBAAAABBAAAABAAABB";
>
> I want to know how many "BB" patterns there are... is there a function

that
> exists to do this already or do I need to roll my own?
>
> Thanks,
> B
>
>

response again, formatted properly:

Pattern matching is done with something called regular language recognition.

If you're not familiar with this, read up on "deterministic finite
automata". By implementing a little state machine, you could do what you
want.

 Siemel Naran 08-24-2004 05:19 AM

Re: Pattern match question

"Victor Bazarov" <v.Abazarov@comAcast.net> wrote in message news:0KqWc.189

> > What is the best way to find out how many times a pattern is matched in

a
> > string? For example if I have:
> >
> > std::string s = "AAAAABBAAAABBAAAABAAABB";
> >
> > I want to know how many "BB" patterns there are... is there a function

that
> > exists to do this already or do I need to roll my own?

>
> You could write a [simple enough] predicate for 'count_if', given that
> "BBB" has two 'BB' patterns, or you need to roll your own if "BBB" should
> only have one.

How to do this? The predicate of count_if can only check one char at a
time. I suppose one could do

class IsBB {
public:
explicit IsBB(const char * expect);
bool operator()(const char& arg) const {
const char * a = &lhs;
return strncmp(a, d_expect, strlen(d_expect));
}
private:
const char * d_expect;
};

But it's ugly because in operator()(const char&) we assume that the original
container is a continuous array of chars, which is only true for C style
strings and std::vector<char>, but not std::string and other more exotic
containers.

One could use std::search though.

unsigned int count(const string& s, const string& expect) {
unsigned int count = 0;
typedef string::const_iterator Iter;
Iter iter = s.begin();
const Iter end = s.end();
while (iter!=end) {
Iter find = std::search(iter, end, expect.begin(), expect.end());
if (find == end) break;
++count;
/* either one of the below */
++iter;
iter += expect-end() - expect.begin();
}
return count;
}

 Siemel Naran 08-24-2004 05:30 AM

Re: Pattern match question

"Dave" <better_cs_now@yahoo.com> wrote in message
> "BCC" <bryan@akanta.com> wrote in message

> Pattern matching is done with something called regular language

recognition.
>
> If you're not familiar with this, read up on "deterministic finite
> automata". By implementing a little state machine, you could do what you
> want.

The std::search is worst case O(n*m) where n is the length of the string we
are searching and m is the length of the expected string. It's average case
is O(n) though.

The automata would be best and worst case O(n). But we have to construct
the automata which is I think is at least O(m^2), and traversing each char
in the string is possibly a little longer. But regular text editors usually
use this elaborate approach.

 Alex Vinokur 08-24-2004 06:03 AM

Re: Pattern match question

"BCC" <bryan@akanta.com> wrote in message news:ZqqWc.11290\$fO.4989@newssvr29.news.prodigy.co m...
> What is the best way to find out how many times a pattern is matched in a
> string? For example if I have:
>
> std::string s = "AAAAABBAAAABBAAAABAAABB";
>
> I want to know how many "BB" patterns there are... is there a function that
> exists to do this already or do I need to roll my own?
>
> Thanks,
> B
>
>

Something like?

--------- C++ code ---------
#include <string>
#include <iostream>
#include <cassert>
using namespace std;

typedef unsigned long ulong;

ulong get_pattern_times (const string& str_i, const string& pattern_i)
{
assert (!pattern_i.empty());

ulong ret = 0;
ulong pos = 0;

while ((pos = str_i.find (pattern_i, pos)) != string::npos)
{
ret++;
if (++pos == str_i.size()) break;
}

return ret;

}

int main()
{
cout << get_pattern_times ("AAAAABBBAAAABBAAAABAAABB", "BB") << endl;
return 0;
}

----------------------------

--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

 All times are GMT. The time now is 01:57 PM.