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

本文关键字：快吗 检查 是否 我可以 | 更新日期: 2023-09-27 17:53:21

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

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

这是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的开始)向前扫描。

相关文章：