1

对于固定子字符串搜索，恰好有两种已知算法具有 O(n) 运行时间和 O(1) 工作空间：SMOA 和 Two-Way（参见http://www-igm.univ-mlv.fr/~lecroq/字符串/ )。它们都依赖于对字母表进行排序或强加排序。

假设我不想搜索固定的子字符串，而是希望能够搜索用括号表达式表示的一组子字符串中的任何一个，例如

 [abc]d

将匹配“ad”、“bd”或“cd”。假设字母表是有限的，任何括号的长度都是有界的，因此在时间或空间要求中任何形式为“括号长度”的项都是 O(1)。

有没有办法在 O(n) 时间内执行搜索（n要搜索的字符串的长度在哪里，即“干草堆”）和 O(1) 工作空间？

除非解决方案涉及以某种方式使用字母顺序对括号集进行排序，否则该问题的任何解决方案都将为 O(n)/O(1) 中的固定子字符串搜索问题提供新的解决方案，而无需排序要求，因此似乎不太可能存在。

4

1 回答 1

0

我肯定错过了什么。从您的链接页面中，蛮力方法是 O(n)。看起来你可以很容易地写出你正在寻找的东西：

1.  Pattern is P with index p indicating which element of the pattern we are on.
2.  String is S with index s indicating which element of the string we are on.
3.  if S[s] matches P[p], increment both indicies and repeat until you complete the Pattern.
4.  If S[s] doesn't match P[p], set p=0 and increment p.

那将是 O(n) 并满足您的要求。

于 2012-08-27T18:28:20.210 回答