我想查找具有特定短字符串数组或链表的字符串。我做了一个小程序，用 c++ 搜索会议或研讨会 http://dblp.uni-trier.de/。我想知道的是如何在数组或链表中快速搜索字符串。当使用 string.find(( 函数时，我认为如果数组的长度为 n，则此函数的性能具有 O(n( 时间复杂度。我可以提高低于 O(n( 的性能吗？请帮帮我
对于数组，除非对其进行排序，否则您能做的最好的事情是 O(n( 平均值/最坏情况，因为您必须线性查看，直到找到所需的字符串。如果它被排序(这将需要 O(nlog(n(( 进行排序(，您可以使用二叉搜索使其成为 O(log(n(( 搜索。对于链表，无论排序如何，您能做的最好的事情就是 O(n(。
如果你真的想使你的代码复杂化，在每次插入列表时，将指向节点的指针存储在某个平衡树中。其中将根据该节点比较中的字符串插入节点。 然后你可以在O(logn(时间内得到字符串。
如果你想获得快速检索，使用哈希映射，它会给你O(1(时间。