algorithm - 在字符串数组中查找字符串的最快算法？

Question

这个问题只是关于算法的。 在伪代码中是这样的:

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

这个for循环需要进行N次字符串比较(或者字节比较N*M次，O(N*M))。当数组 A 有很多项，或者当字符串 S 太长时，这很糟糕。

有没有更好的方法来找出第一次出现的情况？ O(K*logK) 的某些算法是可以的，但最好是 O(K) 或最佳 O(logK)，其中 K 是 N 或 M。

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

Answer 1

您可以将整个字符串数组转换为有限状态机，其中转换是字符串的字符，并将产生状态的字符串的最小索引放入状态。这会花费很多时间，并且可以考虑编制索引。