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

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

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