c# - 我可以检查子序列是否比 O(n*n) 更快

Question

所以我的问题是主题名称。是否存在一种算法可以比 O(N^2) 更快地检查 B 是否是 A 的子序列，例如 O(NlogN) 或简单的 O(N)？

找到的唯一方法是简单的蛮力

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

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 的长度上。