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

所以我的问题是主题的名称。是否存在一种算法可以比 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;

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