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

所以我的问题是主题的名称。是否存在一种算法，该算法检查B是否是A的子序列，比O（N ^ 2）更快，例如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的长度。

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

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