Big O and algorithm to decide string A contains string B?

Discussion in 'C++' started by usgog@yahoo.com, Mar 24, 2005.

  1. Guest

    I need to implement a function to return True/false whether String A
    contains String B. For example, String A = "This is a test"; String B =
    "is is". So it will return TRUE if String A includes two "i" and two
    "s". The function should also handle if String A and B have huge
    values, like two big dictionary.

    What's the best approach to achieve this with the best performance?
    what's the Big O then?

    I am thinking to put A and B into two hashtable, like key = "i" and
    value = "2" and so on. Then compare these two hashtable. But how to
    compare two hashtables? Please advise.
     
    , Mar 24, 2005
    #1
    1. Advertising

  2. Mark P Guest

    wrote:
    > I need to implement a function to return True/false whether String A
    > contains String B. For example, String A = "This is a test"; String B =
    > "is is". So it will return TRUE if String A includes two "i" and two
    > "s". The function should also handle if String A and B have huge
    > values, like two big dictionary.
    >
    > What's the best approach to achieve this with the best performance?
    > what's the Big O then?
    >
    > I am thinking to put A and B into two hashtable, like key = "i" and
    > value = "2" and so on. Then compare these two hashtable. But how to
    > compare two hashtables? Please advise.
    >


    One simple possibility is to iterate through each position i within
    string A and see if the substring A(i,i+length(B)) = B. Java and C++
    have facilities to make this quite simple. The worst case runtime is
    O(length(A)*length(B)) under reasonable assumptions about how string
    comparisons are performed.

    Perhaps one can do better if one is clever.
     
    Mark P, Mar 24, 2005
    #2
    1. Advertising

  3. "Mark P" <> wrote in message
    news:HFu0e.14995$...
    >
    > One simple possibility is to iterate through each position i within string
    > A and see if the substring A(i,i+length(B)) = B. Java and C++ have
    > facilities to make this quite simple. The worst case runtime is
    > O(length(A)*length(B)) under reasonable assumptions about how string
    > comparisons are performed.


    Way too slow if your pattern is 1k chars long and your text is 5 million
    chars long (one small gene).

    > Perhaps one can do better if one is clever.


    Hmmm . . . the Manber-Meyers suffix array algorithm is O(n + log m) where n
    is the size of the pattern and m is the length of the text (this is after
    suffix array construction, which is . . . O(n), I think, for suffix tree
    (O(n)) then tree -> array (O(n))). This algorithm is independent of
    alphabet size. I can't find a version of it on the internet, and by no
    means will I explain it to you.

    The phrase "DO YOUR OWN HOMEWORK" comes to mind as well. Please.

    - JFA1
     
    James Aguilar, Mar 24, 2005
    #3
  4. Siemel Naran Guest

    <> wrote in message

    > I need to implement a function to return True/false whether String A
    > contains String B. For example, String A = "This is a test"; String B =
    > "is is". So it will return TRUE if String A includes two "i" and two
    > "s". The function should also handle if String A and B have huge
    > values, like two big dictionary.


    Because String B = "is is" (note the space), should the function return true
    if String A contains two "i", two "s", one space?

    The first step would be to parse String B so that we know to expect 2 "i", 2
    "s", 1 " ".

    What's the number of distinct chars? Is it A-Z and a-z for a total of 52?
    If the number of distinct chars is small, say 256 distinct chars, create an
    array, such as unsigned expect[256], to represent the number of chars to
    expect. expect['i'] would equal 2, expect['s'] would equal 2, expect[' ']
    would equal 1, and all other expect elements would be zero. If the number
    of distinct chars is large, then you could use a map<char_type, unsigned> or
    hashtable.

    Now step through every char in String A. Let the char in question be char
    c. Decrement expect[c] by one, but if it is zero then don't decrement it.
    Now check if all the elements in expect are zero. As an optimization, you
    only need to do this check if you decremented expect[c].

    To check if all the elements in expect are zero, you could for example
    create another array zero, such as unsigned zero[256] = {0}, and use memcmp
    to compare expect to zero. There are other ways, maybe platform specific
    ways that might be faster.

    Remember to deal with the special case that String B is the empty string, in
    which case you can probably immediately return true.

    > What's the best approach to achieve this with the best performance?
    > what's the Big O then?


    My algorithm is O(length(String A)) + O(length(String B)).

    > I am thinking to put A and B into two hashtable, like key = "i" and
    > value = "2" and so on. Then compare these two hashtable. But how to
    > compare two hashtables? Please advise.


    In principle it is doable, but putting all the chars of String A into a
    hashtable might be rather expensive.

    To compare two hashtables, you could iterate through the elements in the
    first hash table, using a for_each(hash1.begin(), hash1.end()) structure, or
    even for (Iter iter = hash1.begin(); iter != hash1.end(); ++iter). For each
    element in hash1, look up the corresponding value in hash2, for example
    hash2[iter->key]. Then check if the values are equal, for example
    iter->value == hash2[iter->key].
     
    Siemel Naran, Mar 24, 2005
    #4
  5. Guest

    Thanks for ur input! This topic is open to discuss the algorithm
    actually.
     
    , Mar 24, 2005
    #5
  6. Guest

    I do not quite undertstand the problem. You write that the function
    should return true when string A contains string B. But your example
    shows that it should return true when string A contains all characters
    that are in string B. This is something very different. Which one is
    your problem?

    cheers,
    Marcin Kalicinski
     
    , Mar 24, 2005
    #6
  7. You can use the Rabin-Karrp alghoritm

    with average access time O(n+m) in the common case.



    <> ha scritto nel messaggio
    news:...
    > I need to implement a function to return True/false whether String A
    > contains String B. For example, String A = "This is a test"; String B =
    > "is is". So it will return TRUE if String A includes two "i" and two
    > "s". The function should also handle if String A and B have huge
    > values, like two big dictionary.
    >
    > What's the best approach to achieve this with the best performance?
    > what's the Big O then?
    >
    > I am thinking to put A and B into two hashtable, like key = "i" and
    > value = "2" and so on. Then compare these two hashtable. But how to
    > compare two hashtables? Please advise.
    >
     
    Marco Cassiani, Mar 24, 2005
    #7
  8. <> schrieb im Newsbeitrag
    news:...
    >I need to implement a function to return True/false whether String A
    > contains String B. For example, String A = "This is a test"; String
    > B =
    > "is is". So it will return TRUE if String A includes two "i" and two
    > "s". The function should also handle if String A and B have huge
    > values, like two big dictionary.
    >
    > What's the best approach to achieve this with the best performance?
    > what's the Big O then?
    >
    > I am thinking to put A and B into two hashtable, like key = "i" and
    > value = "2" and so on. Then compare these two hashtable. But how to
    > compare two hashtables? Please advise.
    >


    bool XY(const char* src, const char* seek)
    {
    std::map<char, int> counter;
    std::map<char, int>::iterator it;

    // Fill map with number of chars in dest
    for(; *seek!='\0'; ++seek)
    {
    if(is_char_to_be_counted(*seek))
    ++counter[*seek];
    }
    // subtract the count of these chars on src
    for(; *src!='\0'; ++src)
    {
    it = counter.find(*src);
    if(it!=counter.end() && --it->second<0)
    return false; // src has more 'x's than dest
    }
    // See if any of these has different count
    for(it=counter.begin(); it!=counter.end(); ++it)
    {
    if(it->second) return false; // dest has more 'x's than src
    }
    return true;
    }

    this should so the trick quickly. If you really have chars, you can
    replace the std::map with a simple array of 256 ints...
    -Gernot
     
    Gernot Frisch, Mar 24, 2005
    #8
  9. Guest

    Acutally the problem is not about String Matching. The function will
    return TRUE if string A contains all characters
    that are in string B. Or String A has what String B has. For example,
    String B is "issi" and String A is "This is a test", the function will
    return TRUE. So what if String A and B have big values, what's the best
    algorithm and Big O to achieve this?

    I am thinking creating two hashtable. For String B, key=i, value=2;
    key=s, value=2. For String A, key=i, value=2; key=s, value=3, etc. Then
    compare this two hashtable. So constructing these two hashtable will be
    expensive but the Big O will be O(nlogn). Is it good?
     
    , Mar 24, 2005
    #9
  10. Willem Guest

    wrote:
    ) Acutally the problem is not about String Matching. The function will
    ) return TRUE if string A contains all characters
    ) that are in string B. Or String A has what String B has. For example,
    ) String B is "issi" and String A is "This is a test", the function will
    ) return TRUE. So what if String A and B have big values, what's the best
    ) algorithm and Big O to achieve this?
    )
    ) I am thinking creating two hashtable. For String B, key=i, value=2;
    ) key=s, value=2. For String A, key=i, value=2; key=s, value=3, etc. Then
    ) compare this two hashtable. So constructing these two hashtable will be
    ) expensive but the Big O will be O(nlogn). Is it good?

    Why a hashtable ? There are only 256 different characters, so you
    can just make an array with 256 entries and count.

    The BigO will be O(n).


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Mar 24, 2005
    #10
  11. Guest

    Yes. An array with 256 entries should be enough. But how to create an
    array using char as the index? array index is supposed to be int,
    right? For example, array[0] = 'a' instead of array['a'] = 0. Sorry, I
    am a newbie to algorithm...
     
    , Mar 25, 2005
    #11
  12. wrote:
    >
    > Yes. An array with 256 entries should be enough. But how to create an
    > array using char as the index? array index is supposed to be int,
    > right?


    a char is nothing more then a small integer in C and C++. Only
    during input and output a char is treated differently.

    > For example, array[0] = 'a' instead of array['a'] = 0. Sorry, I
    > am a newbie to algorithm...


    array['a'] = 0;

    is fine. (Remember: a char is nothing more then an small integer. Its
    value is the code number of the character on your system).

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Mar 25, 2005
    #12
  13. msalters Guest

    wrote:
    > Yes. An array with 256 entries should be enough. But how to create an
    > array using char as the index? array index is supposed to be int,
    > right? For example, array[0] = 'a' instead of array['a'] = 0. Sorry,

    I
    > am a newbie to algorithm...


    char is an integral type, like short, int and long. They'll convert
    without problems. i.e.

    int frequency[ 1<<CHAR_BIT ] = {0}; // typically 256 entries
    std::string A = foo();
    for( int i=0;i!=A.size(); ++i )
    ++frequency[ A ];

    std::string B = bar();
    for( int i=0;i!=B.size(); ++i )
    if( frequency[ B ]-- == 0 )
    std::cout << "B not in A";

    Obvious O(A.size+B.size) and you can't do better
    in general.

    HTH,
    Michiel Salters
     
    msalters, Mar 25, 2005
    #13
  14. "msalters" <> wrote in message
    news:...
    >
    > wrote:
    > > Yes. An array with 256 entries should be enough. But how to create an
    > > array using char as the index? array index is supposed to be int,
    > > right? For example, array[0] = 'a' instead of array['a'] = 0. Sorry,

    > I
    > > am a newbie to algorithm...

    >
    > char is an integral type, like short, int and long. They'll convert
    > without problems. i.e.
    >
    > int frequency[ 1<<CHAR_BIT ] = {0}; // typically 256 entries
    > std::string A = foo();
    > for( int i=0;i!=A.size(); ++i )
    > ++frequency[ A ];
    >
    > std::string B = bar();
    > for( int i=0;i!=B.size(); ++i )
    > if( frequency[ B ]-- == 0 )
    > std::cout << "B not in A";
    >
    > Obvious O(A.size+B.size) and you can't do better
    > in general.
    >
    > HTH,
    > Michiel Salters
    >


    std:string is represented as 'char's which can be signed or unsigned
    depending on the platform, so you probably want e.g. ++frequency[A &
    0xff].

    --
    Roger
     
    Roger Willcocks, Mar 25, 2005
    #14
  15. "Willem" <> wrote in message
    news:...
    > wrote:
    > ) Acutally the problem is not about String Matching. The function will
    > ) return TRUE if string A contains all characters
    > ) that are in string B. Or String A has what String B has. For example,
    > ) String B is "issi" and String A is "This is a test", the function will
    > ) return TRUE. So what if String A and B have big values, what's the best
    > ) algorithm and Big O to achieve this?
    > )
    > ) I am thinking creating two hashtable. For String B, key=i, value=2;
    > ) key=s, value=2. For String A, key=i, value=2; key=s, value=3, etc. Then
    > ) compare this two hashtable. So constructing these two hashtable will be
    > ) expensive but the Big O will be O(nlogn). Is it good?
    >
    > Why a hashtable ? There are only 256 different characters, so you
    > can just make an array with 256 entries and count.
    >
    > The BigO will be O(n).
    >
    >
    > SaSW, Willem
    > --
    > Disclaimer: I am in no way responsible for any of the statements
    > made in the above text. For all I know I might be
    > drugged or something..
    > No I'm not paranoid. You all think I'm paranoid, don't you !
    > #EOT


    You cross post this in a Jav newsgroup and have the cheek to suggest that
    there are only 256 characters ! That's why I abandoned C and it's
    derivatives... which simply assumed that nobody in China, Japan, Korea etc
    would ever need to use a computer ;-)
     
    Pointless Harlows, Apr 9, 2005
    #15
  16. Pointless Harlows wrote:
    >
    > "Willem" <> wrote in message
    > news:...
    > > wrote:
    > > ) Acutally the problem is not about String Matching. The function will
    > > ) return TRUE if string A contains all characters
    > > ) that are in string B. Or String A has what String B has. For example,
    > > ) String B is "issi" and String A is "This is a test", the function will
    > > ) return TRUE. So what if String A and B have big values, what's the best
    > > ) algorithm and Big O to achieve this?
    > > )
    > > ) I am thinking creating two hashtable. For String B, key=i, value=2;
    > > ) key=s, value=2. For String A, key=i, value=2; key=s, value=3, etc. Then
    > > ) compare this two hashtable. So constructing these two hashtable will be
    > > ) expensive but the Big O will be O(nlogn). Is it good?
    > >
    > > Why a hashtable ? There are only 256 different characters, so you
    > > can just make an array with 256 entries and count.
    > >
    > > The BigO will be O(n).
    > >
    > >
    > > SaSW, Willem
    > > --
    > > Disclaimer: I am in no way responsible for any of the statements
    > > made in the above text. For all I know I might be
    > > drugged or something..
    > > No I'm not paranoid. You all think I'm paranoid, don't you !
    > > #EOT

    >
    > You cross post this in a Jav newsgroup and have the cheek to suggest that
    > there are only 256 characters ! That's why I abandoned C and it's
    > derivatives... which simply assumed that nobody in China, Japan, Korea etc
    > would ever need to use a computer ;-)
    >

    No, C just assumes that people in China, Japan, Korea, and India will use
    computers in English!!! ;-)


    --
    +----------------------------------------------------------------+
    | Charles and Francis Richmond It is moral cowardice to leave |
    | undone what one perceives right |
    | richmond at plano dot net to do. -- Confucius |

    +----------------------------------------------------------------+
     
    Charles Richmond, Apr 10, 2005
    #16
    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. James Dyer
    Replies:
    5
    Views:
    665
  2. Shaguf
    Replies:
    0
    Views:
    517
    Shaguf
    Dec 24, 2008
  3. Shaguf
    Replies:
    0
    Views:
    479
    Shaguf
    Dec 26, 2008
  4. Shaguf
    Replies:
    0
    Views:
    257
    Shaguf
    Dec 26, 2008
  5. Shaguf
    Replies:
    0
    Views:
    236
    Shaguf
    Dec 24, 2008
Loading...

Share This Page