找到字符串数组中的字符串的最快算法？

这个问题只是关于算法。在伪码是这样的：找到字符串数组中的字符串的最快算法？

A = Array of strings; //let's say count(A) = N 
S = String to find; //let's say length(S) = M 

for (Index=0; Index<count(A); Index++) 
    if (A[Index]==S) { 
    print "First occurrence at index\x20"+Index; 
    break; 
    }

这对于回路需要字符串比较N次（或字节比较N * M次，O（N * M））。当数组A有很多项目，或者当字符串S太长时，这是不好的。

任何找到第一个出现的更好方法？ O（K * logK）上的一些算法是可以的，但是在O（K）或O（logK）时最好，其中K是N或M.

我不介意在某些其他结构中添加或在比较循环之前做一些数据处理。

来源

2012-04-28 jondinham

“当字符串S太长时”是不相关的，除非'A中有很多字符串'具有相同的长度和相同的长前缀。（如果长度不同，则字符串相等性检查可以立即终止，或者一旦发现不匹配，就立即终止。） – Dougal 2012-04-28 18:43:58

为什么使用'\ x20'而不是空格？我很好奇:-) – 2012-04-28 18:46:01

哦，是的，比较时间更多地取决于阵列中的字符串的长度A – jondinham 2012-04-28 18:46:24

您可以将整个字符串数组转换为有限状态机，其中转换是字符串的字符，并将生成状态的字符串的最小索引置于状态。这需要很长时间，并且可能被视为索引。

来源

2012-04-28 18:42:49 Reactormonk

更多地被称为[trie]（http://en.wikipedia.org/wiki/Trie）。 – Dougal 2012-04-28 18:47:02

[f] lex可以帮助您构建此DFA。 – wildplasser 2012-04-28 18:47:06

@Dougal感谢您的名字，不知道。 – Reactormonk 2012-04-28 19:20:00

将字符串放入基于散列的集合中，并测试以查看给定字符串是否包含在集合中，一旦集合被构建，应该会给您提供更多或更少的恒定性能。

来源

2012-04-28 18:40:46 Bill

如果您想查找索引，请使用基于哈希的字符串字典 - >第一次出现。 – Dougal 2012-04-28 18:41:21

但我有点担心有些2个项目可能具有相同的散列值 – jondinham 2012-04-28 18:44:08

那么，你需要做最后的比较，给定相同的散列值。 – wildplasser 2012-04-28 18:46:17

您可以先排序字符串数组，这将花费O（m * nlogn）时间。在A排序之后，您可以执行二分搜索而不是线性搜索，这可以将总运行时间减少到O（m * logn）。

这种方法的优点是它很容易实现。例如，在Java中，只需2行代码即可完成此操作：

Arrays.sort(A); 
int index = Arrays.binarySearch(A, "S");

来源

2012-04-28 18:57:44 Nova2358

二进制搜索之前的排序过程占用大部分时间，是不是 – jondinham 2012-04-28 19:25:02

@PaulDinh它需要O（M N log N）时间。 – Dougal 2012-04-28 19:27:01

@PaulDinh我认为在实践中时间确定。在最坏的情况下，它的剂量需要O（M N log N）时间。但加载所有的字符串将需要M * N次，所以它只比log IO记录长n倍。在大多数情况下，log n非常小，甚至可能比在实践中构建一个trie或hashtable更快。如果你关心理论上的时间复杂度，那么建立一个特里或散列表将花费O（M * N）时间。 – Nova2358 2012-04-29 03:11:01

您可以使用Self-balancing binary search tree。大多数实现都要插入O（log（n）），并且要O（log（n））进行搜索。如果你的集合不是很大，并且你的值有很好的散列函数，那么基于散列的集合是一个更好的解决方案，因为在这种情况下，你将有O（1）插入和O（1）寻找。但是如果你的散列函数不好，或者你的散列函数太大，那么插入O（n）就可以搜索。

来源

2012-04-28 19:02:57

以尽可能快的搜索，最好的办法，是让数组排序正如你所说，似乎是没有可能的信息先验这将允许在搜索

排序一些启发或约束数组第一个（快速排序例如O（NlogN）），并执行二进制搜索接下来O（log（N））

来源

2012-04-28 19:06:13 jpmuc

找到字符串数组中的字符串的最快算法？

回答

相关问题