Velocity Reviews > C++ > Big O and algorithm to decide string A contains string B?

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

usgog@yahoo.com
Guest
Posts: n/a

 03-24-2005
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

Mark P
Guest
Posts: n/a

 03-24-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
>

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.

James Aguilar
Guest
Posts: n/a

 03-24-2005
"Mark P" <(E-Mail Removed)> wrote in message
news:HFu0e.14995\$(E-Mail Removed) om...
>
> 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

Siemel Naran
Guest
Posts: n/a

 03-24-2005
<(E-Mail Removed)> 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

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

usgog@yahoo.com
Guest
Posts: n/a

 03-24-2005
Thanks for ur input! This topic is open to discuss the algorithm
actually.

kalita@poczta.onet.pl
Guest
Posts: n/a

 03-24-2005
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

cheers,
Marcin Kalicinski

Marco Cassiani
Guest
Posts: n/a

 03-24-2005
You can use the Rabin-Karrp alghoritm

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

<(E-Mail Removed)> ha scritto nel messaggio
news:(E-Mail Removed) ups.com...
> 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
>

Gernot Frisch
Guest
Posts: n/a

 03-24-2005

<(E-Mail Removed)> schrieb im Newsbeitrag
news:(E-Mail Removed) ups.com...
>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
>

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

usgog@yahoo.com
Guest
Posts: n/a

 03-24-2005
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?

Willem
Guest
Posts: n/a

 03-24-2005
(E-Mail Removed) 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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Shaguf ASP .Net 0 12-26-2008 09:29 AM Shaguf ASP .Net Web Controls 0 12-26-2008 06:11 AM Shaguf Python 0 12-24-2008 07:35 AM Shaguf Ruby 0 12-24-2008 05:07 AM James Dyer Perl 5 02-20-2004 12:29 PM