Pattern match question

Discussion in 'C++' started by BCC, Aug 23, 2004.

  1. BCC

    BCC Guest

    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
    BCC, Aug 23, 2004
    #1
    1. Advertising

  2. 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
    Victor Bazarov, Aug 23, 2004
    #2
    1. Advertising

  3. BCC

    Dave Guest

    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:ZqqWc.11290$...
    > 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, Aug 23, 2004
    #3
  4. BCC

    Dave Guest

    "BCC" <> wrote in message
    news:ZqqWc.11290$...
    > 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.
    Dave, Aug 23, 2004
    #4
  5. BCC

    Siemel Naran Guest

    "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<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, Aug 24, 2004
    #5
  6. BCC

    Siemel Naran Guest

    "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.
    Siemel Naran, Aug 24, 2004
    #6
  7. BCC

    Alex Vinokur Guest

    "BCC" <> wrote in message news:ZqqWc.11290$...
    > 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
    Alex Vinokur, Aug 24, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. hiwa
    Replies:
    0
    Views:
    628
  2. Chris

    Pattern Match Question

    Chris, Jun 4, 2008, in forum: Java
    Replies:
    5
    Views:
    379
    Roedy Green
    Jun 4, 2008
  3. Rodney

    Pattern Match Question..

    Rodney, Sep 13, 2003, in forum: Perl Misc
    Replies:
    2
    Views:
    89
    Rodney
    Sep 14, 2003
  4. Replies:
    5
    Views:
    133
    Tad McClellan
    Jan 15, 2005
  5. Allan M. Due
    Replies:
    5
    Views:
    94
    A. Sinan Unur
    Nov 13, 2005
Loading...

Share This Page