Big O和决定字符串A的算法包含字符串B？ [英] Big O and algorithm to decide string A contains string B?

问题描述

我需要实现一个返回True / false的函数，无论字符串A

是否包含字符串B.例如，字符串A =这是一个测试;字符串B =

" is is。因此，如果字符串A包括两个i，则它将返回TRUE。和两个

s。如果字符串A和B具有巨大的价值，例如两个大字典，该函数也应该处理。


实现这一目标的最佳方法是什么？最好的表现？

什么是Big O呢？


我想把A和B分成两个哈希表，比如key =" I"和

value =" 2"等等。然后比较这两个哈希表。但是如何比较两个哈希表？
？请指教。

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.

推荐答案

我们*** @ yahoo.com 写道：

我需要实现一个函数来返回True / false是否字符串A
包含字符串B.例如，字符串A =这是一个测试英寸;字符串B =
is is。因此，如果字符串A包括两个i，则它将返回TRUE。和两个
s。如果字符串A和B具有巨大的值，例如两个大字典，该函数也应该处理。

以最佳性能实现这一目标的最佳方法是什么？
什么是大O呢？

我想把A和B分成两个哈希表，比如key =" i"和
值=" 2"等等。然后比较这两个哈希表。但是如何比较两个哈希表呢？请指教。

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.

一个简单的可能性就是在
字符串A中迭代每个位置i并查看子串A（i，i） + length（B））= B. Java和C ++

有设施让这很简单。在关于如何执行字符串

比较的合理假设下，最坏情况的运行时间是

O（长度（A）*长度（B））。

如果一个人聪明，也许可以做得更好。

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.

< us *** @ yahoo.com>在消息中写道

<us***@yahoo.com> wrote in message

我需要实现一个函数来返回True / false是否字符串A
包含字符串B.例如，字符串A =这是一个测试 ;字符串B =
is is。因此，如果字符串A包括两个i，则它将返回TRUE。和两个
s。如果字符串A和B具有巨大的值，例如两个大字典，该函数也应该处理。


因为字符串B =是是（注意空格），如果函数返回true

如果字符串A包含两个i，两个s，一个空格？

第一步是解析字符串B，以便我们知道期望2i，2

s，1。 。


不同字符的数量是多少？它是AZ和az共52个？

如果不同字符的数量很小，比如256个不同的字符，则创建一个

数组，例如unsigned expect [ 256]，表示期望值为
的字符数。期望[''我']等于2，期望['''''等于2，期望['''']

等于1，所有其他期望元素将是零。如果不同字符的数字很大，那么你可以使用地图< char_type，unsigned>或者

哈希表。


现在逐步执行字符串A中的每个字符。让有问题的字符为char

c。递减期望[c]加1，但如果它为零，则不要递减它。

现在检查期望中的所有元素是否为零。作为优化，你只需要进行检查，如果你减少了期望[c]。


要检查期望的所有元素是否为零，你可以举例如：
创建另一个数组零，例如无符号零[256] = {0}，并使用memcmp

将expect与零进行比较。还有其他方法，可能是平台特定的

可能更快的方式。


请记住处理字符串B是空字符串的特殊情况，

在哪种情况下你可以立即返回true。

以最佳性能实现这一目标的最佳方法是什么？
什么是大的哦呢？


我的算法是O（长度（字符串A））+ O（长度（字符串B））。

我想把A和B放进去两个哈希表，如key =" i"和
值=" 2"等等。然后比较这两个哈希表。但是如何比较两个哈希表呢？请指教。

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.

原则上它是可行的，但将字符串A的所有字符放入

哈希表可能相当昂贵。 br />

要比较两个哈希表，你可以使用for_each（hash1.begin（），hash1.end遍历

第一个哈希表中的元素。 ））结构，或者

甚至（Iter iter = hash1.begin（）; iter！= hash1.end（）; ++ iter）。对于hash1中的每个

元素，在hash2中查找相应的值，例如

hash2 [iter-> key]。然后检查值是否相等，例如

iter-> value == hash2 [iter-> key]。

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

I没有完全解决问题。你写的是当字符串A包含字符串B时，函数

应该返回true。但是你的例子

表明当字符串A包含所有字符时它应该返回true
字符串B中的
。这是非常不同的。哪一个是

你的问题？


欢呼，

Marcin Kalicinski

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

这篇关于Big O和决定字符串A的算法包含字符串B？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！