By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,131 Members | 1,882 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,131 IT Pros & Developers. It's quick & easy.

Pattern match question

P: n/a
BCC
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
Jul 22 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
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
Jul 22 '05 #2

P: n/a
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" <br***@akanta.com> wrote in message
news:Zq*****************@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

Jul 22 '05 #3

P: n/a

"BCC" <br***@akanta.com> wrote in message
news:Zq*****************@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


Please forgive and ignore my earlier inadvertent top-post. Here's my
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.

Jul 22 '05 #4

P: n/a
"Victor Bazarov" <v.********@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;
}

Jul 22 '05 #5

P: n/a
"Dave" <be***********@yahoo.com> wrote in message
"BCC" <br***@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.
Jul 22 '05 #6

P: n/a

"BCC" <br***@akanta.com> wrote in message news:Zq*****************@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


Jul 22 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.