我的问题是关于主题名称的。是否存在一种算法可以更快地检查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;
我的问题是关于主题名称的。是否存在一种算法可以更快地检查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;
是的,可以使用Knuth, Morris and Pratt算法比O(n^2)
更快地完成。但请注意框架提供的实现可能已经实现了此算法。
是的,以下贪心算法是正确的,并且在O(n)时间内运行。对于B中的每个元素,按顺序从A的前一个停止点(最初为A的开头)向前扫描,寻找第一次出现的位置。
IsSubsequence
代码。 - Niklas B.