Well, no, not really. Not that it matters, since the naive "obvious" approach is already O(n).
| [reply] |
Some background context:
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).
| [reply] |
$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];
}
Result:
I found a match, at offset 5 and with total length 19
| [reply] [d/l] [select] |
/^[^a]*?a[^b]*?b[^c]*?c[^d]*?d/
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.
| [reply] [d/l] |