446,131 Members | 1,882 Online
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 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
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" 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" 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" 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, 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" wrote in message "BCC" 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" 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 #include #include 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.