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

[usgog@yahoo.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
compare two hashtables? Please advise.

[Mark P]

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

usgog@yahoo.com wrote:[color=blue]
> 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.
>[/color]

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)*len gth(B)) under reasonable assumptions about how string
comparisons are performed.

Perhaps one can do better if one is clever.

[Siemel Naran]

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

<usgog@yahoo.co m> wrote in message
[color=blue]
> 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.[/color]

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.
[color=blue]
> What's the best approach to achieve this with the best performance?
> what's the Big O then?[/color]

My algorithm is O(length(String A)) + O(length(String B)).
[color=blue]
> 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.[/color]

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

[kalita@poczta.onet.pl]

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

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

[Gernot Frisch]

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


<usgog@yahoo.co m> schrieb im Newsbeitrag
news:1111648920 .271022.36510@o 13g2000cwo.goog legroups.com...[color=blue]
>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.
>[/color]

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_b e_counted(*seek ))
++counter[*seek];
}
// subtract the count of these chars on src
for(; *src!='\0'; ++src)
{
it = counter.find(*s rc);
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]

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

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]

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

usgog@yahoo.com 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

[usgog@yahoo.com]

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

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

[Karl Heinz Buchegger]

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

usgog@yahoo.com wrote:[color=blue]
>
> 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?[/color]

a char is nothing more then a small integer in C and C++. Only
during input and output a char is treated differently.
[color=blue]
> For example, array[0] = 'a' instead of array['a'] = 0. Sorry, I
> am a newbie to algorithm...[/color]

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
kbuchegg@gascad .at

[msalters]

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


usgog@yahoo.com wrote:[color=blue]
> 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,[/color]
I[color=blue]
> am a newbie to algorithm...[/color]

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[i] ];

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

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

HTH,
Michiel Salters

[Roger Willcocks]

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

"msalters" <Michiel.Salter s@logicacmg.com > wrote in message
news:1111747133 .444717.258320@ l41g2000cwc.goo glegroups.com.. .[color=blue]
>
> usgog@yahoo.com wrote:[color=green]
> > 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,[/color]
> I[color=green]
> > am a newbie to algorithm...[/color]
>
> 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[i] ];
>
> std::string B = bar();
> for( int i=0;i!=B.size() ; ++i )
> if( frequency[ B[i] ]-- == 0 )
> std::cout << "B not in A";
>
> Obvious O(A.size+B.size ) and you can't do better
> in general.
>
> HTH,
> Michiel Salters
>[/color]

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[i] &
0xff].

--
Roger

[Pointless Harlows]

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


"Willem" <willem@stack.n l> wrote in message
news:slrnd46ebs .2bh3.willem@to ad.stack.nl...[color=blue]
> usgog@yahoo.com 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[/color]

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

[Charles Richmond]

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

Pointless Harlows wrote:[color=blue]
>
> "Willem" <willem@stack.n l> wrote in message
> news:slrnd46ebs .2bh3.willem@to ad.stack.nl...[color=green]
> > usgog@yahoo.com 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[/color]
>
> 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 ;-)
>[/color]
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 |

+----------------------------------------------------------------+

[Robert Maas, see http://tinyurl.com/uh3t]

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

> From: "Pointless Harlows" <pointless_nopi nkmeat@btintern et.com>[color=blue]
> You cross post this in a Jav newsgroup and have the cheek to suggest
> that there are only 256 characters ![/color]

The original poster included a C++ group, where 8-bit characters are
generally assumed, and the example shown is purely ASCII, so it was a
natural assumption that "character" meant either 7-bit ASCII stored in
8-bit bytes with high bit zero or 8-bit extended-ASCII with
platform-dependent semantics such as latin-1.

However you have a good point that it was *also* posted to a Java
group, where the original characters were a 16-bit subset of Unicode
and later changed to UTF-16 and even more recently redefined as 32-bit
bytes. With so many possible characters, it's hopelessly slow to build
a lookup table. But a map (hashtable or binary tree) isn't necessary if
the data consists of text from any natural language or combination
thereof. A very few characters appear very commonly, such as space and
'e' and 't' in English, while the majority of characters almost never
appear. The optimum data structure might be a simple linear list, with
linear search, sorted per descending occurance count, so that most
searches reach their target very quickly. When you put a new character
in the table, you put it after the last already-existing character.
When you increment a count of an old character, you bubble it forward
if its count now exceeds its predecessor's count. After you've finished
building a table from a string, if you want to use it as a lookup table
for comparing two such tables, and it's too large to efficiently search
linearily, you can then sort it by UniCode value so as to be able to
use binary search for the lookups. But in most practical cases
continuing to do linear lookup should be fast enough. Actually, the
time to build the table is larger than the time to scan it once, so
don't bother sorting it unless the string you've scanned is constant
and the linear-search table is large and you'll be comparing it many
times.

By the way, the Subject field is misleading. What you really are doing
is testing whether multiset B is subset of multiset A, where the
elements happen to be characters and they happen to be given as
parameters as if they were strings. So one obvious way to solve the
problem is to convert each string to an explicit multiset, discarding
all sequence information from the strings, then compare the multisets.
In some programming languages there might already be a built-in API
method for comparing multisets, something like
static boolean isSubsetOf(Mult iSet B, MultiSet A);
or
[instance method] boolean isSubsetOf(Mult iSet A);
not to mention a constructor that converts from strings:
MultiSet(String s);
Although I've written those as if part of the Java API, whether
anything resembling that is already in the Java API is unknown to me
and not worth checking right now. But anybody actually planning to
implement the algorithm in Java should check the API documentation to
see if anything like it is available before re-inventing the wheel
yourself. (See also the thread on reusable software components.)