2

将已知字符串与字符串数组进行比较以查看给定字符串是否与数组中的任何字符串匹配，最有效的方法是什么？

例如：你有

string String1 = "ID5";
string String2 = "ID7";

您想查看它们中的任何一个是否包含在以下内容中

string List[5] = {"ID1", "ID7", "ID10", "ID34", "ID62"}

这样你就可以做到这一点

 if(#STRINGMATCHES) {
    // Do one thing
 }
 else {
    // Do another
 }
4

5 回答 5

2

如果您需要多次执行此搜索操作，这就是我的建议 - 使用一些哈希函数对所有字符串进行哈希处理，然后创建一个包含排序哈希的新数组。然后，当您需要检查数组中是否包含字符串时，请在已排序数组中对其哈希进行 binary_search。这将比 als 建议的仅执行 std::find 更有效，但取决于您需要执行足够多次搜索操作以使速度增益弥补排序开销的事实。

于 2012-04-11T07:32:01.740 回答
2

通过使用std::find

std::find(List, List+5, String1)
于 2012-04-11T07:24:04.113 回答
1

如果数组已排序，您可以使用std::binary_search()：

std::string List[] = { "ID1", "ID10", "ID7", "ID34", "ID62" };
if (std::binary_search(std::begin(List), std::end(List), "ID7"))
{
    std::cout << "found string\n";
}

如果不是，则使用std::find()（如 Als 所述）。

于 2012-04-11T07:28:33.640 回答
1

最简单的解决方案是将您要查找的字符串放入一个数组并使用std::find_first_of：

std::string targetList[] = { "ID5", "ID7" };
std::string searchList[] = { "ID1", "ID2", "ID3", "ID4", "ID5" };

if ( std::find_first_of( begin( searchList ), end( searchList ),
                         begin( targetList ), end( targetList ) )
        != end( targetList ) ) {
    //  found...
} else {
    //  not found...
}

这不一定是最有效的解决方案，因为 find_first_of不对数据做任何假设。例如，如果搜索列表很大并且没有变化，并且目标列表只包含几个元素，那么对搜索列表进行排序可能会更有效，并对目标列表中的每个元素进行二分搜索。

于 2012-04-11T07:40:55.157 回答
0

我有个主意。

首先，我们应该使 List 排序。就像 hmjd 描述的那样。

在比较两个字符串时，我们可以记录一些信息。

例如，

表二维数组差异记录两个字符串不同的索引。

string[2] = {"abc","abd"}
list[5] = {"aab","abb","abc","bcd","ef"}



dif[0][0] = 1 ("abc" and "aab" differ at index 1) 
dif[0][1] = 2 ("abc" and "abb" differ at index 2) 
dif[0][2] = -1 ("abc" and "abc" are same, so we use -1 to represent two strings are same) 
dif[0][3] = 0 ("abc" and "bcd" differ at index 0) 
dif[0][4] = 0 ("abc" and "eg" differ at index 0)

当我们需要将一个新字符串与列表中的字符串进行比较时。我们首先在已比较的字符串中找到最相似的字符串。例如，“abd”是需要判断的字符串。我们找到“abc”。"abd" 和 "abc" 在索引 2 处不同。因此，当我们比较 "adb" 和 list 中的字符串时，我们不需要比较在索引 2 之前的索引中不同 "abc" 的字符串。例如，我们不需要比较“abd”和“ef”，因为“abd”在索引 2 处与“abc”不同，而“abc”在索引 0 处与“ef”不同。

我的想法很粗略，有很多细节需要考虑。我认为它很有用，尤其是在大规模问题中。

于 2012-04-12T07:46:26.060 回答