我能否检查子序列是否比O(n*n)更快

Question

我的问题是关于主题名称的。是否存在一种算法可以更快地检查B是否为A的子序列，比如O（NlogN）或简单的O（N），而不是O（N ^ 2）？

唯一找到的方法是简单粗暴。

for(int i = 0; i < a.Length - b.Length; i++)
{
   if (IsSubsequence(a,b,i))
      return i;
}
return -1;

- Alex Zhukovskiy

---

你应该定义子序列并给出一个例子以避免混淆。请添加你的 IsSubsequence 代码。 - Niklas B.

因为通常情况下，子序列的意思与您所询问的不同。 - Niklas B.

Answer 1

这里是David Eisenstat算法的递归描述。（请注意，该算法是尾递归的，因此可以写成循环；我之所以将其描述为递归，是因为这样做是理解该算法的好方法。）

将一个序列定义为空或者是一个项后面跟着一个序列。

取两个序列A和B。问题是B是否是A的子序列。

如果B为空，则B是A的子序列。

如果B不为空且A为空，则B不是A的子序列。

如果我们已经到达这一步，那么A和B都不为空。假设A是项X后面跟着序列C，B是项Y后面跟着序列D。

如果X与Y相同，则问题“B是否是A的子序列？”的答案与较小问题“D是否是C的子序列？”的答案相同。回答这个问题。

如果X与Y不同，则问题“B是否是A的子序列？”的答案与较小问题“B是否是C的子序列？”的答案相同。回答这个问题。

这个过程终止，并且显然它的最坏情况是序列A的长度。

- Eric Lippert

Answer 2

是的，可以使用Knuth, Morris and Pratt算法比O(n^2)更快地完成。但请注意框架提供的实现可能已经实现了此算法。

- Codor

---

子序列，而非子字符串 - Niklas B.

我已经将答案更改为链接到“Contains”方法，而不是“Substring”方法。您说的“子序列”是否完全不同？ - Codor

@Codor：子串是一种特殊的子序列。如果你有序列"A, B, C, D, E"，那么"A, C, E"是一个子序列但不是一个子串。"B, C, D"既是子序列又是子串。子串没有“间隙”。KMP查找的是子串而不是子序列。 - Eric Lippert

感谢您的提醒，我误解了问题。 - Codor

Answer 3

是的，以下贪心算法是正确的，并且在O(n)时间内运行。对于B中的每个元素，按顺序从A的前一个停止点（最初为A的开头）向前扫描，寻找第一次出现的位置。

- David Eisenstat

---

当这里有两个嵌套循环时，您是如何得到O(n)的？ - Alex Zhukovskiy

@AlexJoukovsky它们是嵌套的，因为这是实现它们的方式，但是在一起，内部循环最多只占用A的一个扫描。您可以将它们视为非嵌套的，控制流来回弹跳。 - David Eisenstat