Well, no, not really. Not that it matters, since the naive "obvious" approach is already O(n).

Wikipedia has an explanation of the Knuth-Morris-Pratt algorithm for substring searches.

The difference between a substring and a subsequence is that a subsequence is not necessarily contiguous (all the characters must be present, and in the correct order, but there can be unrelated characters in between).

The difference between a substring and a subsequence is that a subsequence is not necessarily contiguous (all the characters must be present, and in the correct order, but there can be unrelated characters in between).

In that case, I think the easiest way to search for subsequences in Perl is to use regular expressions. For example, if the subsequence is "abcd", then the regular expression to look for a subsequence is /a.*?b.*?c.*?d/.

And since you can easily contruct a regex out of a string, that is easy toconstruct:

$string = 'abcd';
$regex = join '.*?', split //, $string;
$sequence = 'xxxxxaxxxxxxbxxxxxcxxxxdxxxxx';
if($sequence =~ /$regex/s) {
    printf "I found a match, at offset %d and with total length %d\n",
+ $-[0], $+[0]-$-[0];
}
[download]

Result:
I found a match, at offset 5 and with total length 19

If that were to fail to match, then it would fail to match very badly, as in O(N**K) badly. Better:

/^[^a]*?a[^b]*?b[^c]*?c[^d]*?d/
[download]

or use features that I don't use and so don't remember to prevent backtracking. The above version should proceed to match the string linearly and in O(n) and, if that fails, backtrack linearly in O(n) and quickly fail.

- tye