- **C++**
(*http://www.velocityreviews.com/forums/f39-c.html*)

- - **Pattern match question**
(*http://www.velocityreviews.com/forums/t285175-pattern-match-question.html*)

Pattern match questionWhat 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 |

Re: Pattern match questionBCC 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 |

Re: Pattern match questionPattern 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 > > |

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 > > 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. |

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; } |

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. |

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. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.