Can i check if subsequence faster then O(n*n)

问题:

So my question is in topic's name. Does exists an algorithm that checks if B is subsequence of A faster, than O(N^2), for example O(NlogN) or simply O(N)?

Only way found is simple brut-force

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

回答1:

Here's a recursive characterization of David Eisenstat's algorithm. (Note that this algorithm is tail recursive and can therefore be written as a loop; I describe it as recursive because doing so is a nice way to understand the algorithm.)

Define a sequence as either empty, or an item followed by a sequence.

Take two sequences, A and B. The question is if B is or is not a subsequence of A.

If B is empty then B is a subsequence of A.

If B is not empty and A is empty then B is not a subsequence of A.

If we've made it this far, neither A nor B are empty. Suppose that A is item X followed by sequence C and B is item Y followed by sequence D.

If X is the same as Y then the answer to the question "is B a subsequence of A?" is the same as the answer to the smaller question "is D a subsequence of C?". Answer that question.

If X is not the same as Y then the answer to the question "is B a subsequence of A?" is the same as the answer to the smaller question "is B a subsequence of C?". Answer that question.

This procedure terminates and clearly its worst case is in the length of the sequence A.

回答2:

Yes, it can be done faster than O(n^2) with an algorithm by Knuth, Morris and Pratt. However note that the implementation provided by the framework might already implement this algorithm.

回答3:

Yes, the following greedy algorithm is correct and runs in time O(n). For each element of B in order, scan forward in A from the previous stopping point (initially the beginning of A) for the first occurrence.