Regex (PCRE2 v10.35+), 25 bytes
^((.)(?*.*
(\3?+.*\2)))*
Attempt This Online!
Takes input as X followed by Y, delimited by a newline.
This abuses molecular lookahead (?*
...)
to save a byte. Instead of using a lazy quantifier .*?
to advance only as far as necessary to find the next matching character, it greedily lets the regex engine do all the work by backtracking until it is able to match all of X in Y (or fail to, after trying all possibilities).
This beats mbomb007's Retina answer by 1 byte, though not when ported to .NET (in that it is 29 bytes – see below).
Regex (Perl / PCRE / Java), 26 bytes
^((.)(?=.*
(\3?+.*?\2)))*
Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
^ # Anchor to start of string X
(
(.) # \2 = next character from X (starting at its start)
(?= # Atomic lookahead
.*¶ # Skip to the beginning of string Y
( # \3 = concatenation of the following:
\3?+ # previous value of \3, if set
.*? # Advance by as little as possible (minimum zero) to make the
# following match:
\2 # Match the character we captured in \2
)
)
)* # Iterate the above as many times as possible
¶ # Assert that after doing the above, we've reached a newline,
# meaning the loop processed all of string X.
Taking the arguments in the opposite order takes 28 bytes:
((.)(?=.*
(\3?+\2)).*)*
\3?$
Try it online! - PCRE2
Regex (Perl / PCRE / Java / .NET), 29 bytes
^((.)(?=.*
((?>\3?).*?\2)))*
Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - .NET
The uses an atomic group (?>\3?)
instead of a possessive quantifier \3?+
to add .NET compatibility.
Regex (.NET), 31 bytes
(?<=(.)*)
(.*(?<-1>\1))*(?(1)^)
Try it online!
As a matter of curiosity (even though it doesn't beat the group-building method), here is a version using .NET's Balancing Groups feature.
(?<=(.)*) # In a lookbehind, push each character of string X onto the \1
# stack, going from right to left. There is no need to use a "^"
# anchor, because the lookbehind is atomic and will lock in its
# first greedy full match.
¶ # Assert that the next character is a newline, meaning that the
# above processed the entirity of string X.
(
.* # Skip however many characters as needed to match the following:
(?<-1>\1) # Pop a capture off the \1 stack and match it. This is iterated
# from left to right.
)* # Iterate the above as many times as possible.
(?(1)^) # Assert that the \1 stack is now empty (by asserting that if it
# isn't, then we're at the start of the string – which is
# impossible because we have at the very least matched a newline).
Regex (Perl / PCRE / Java / Pythonregex
/ Ruby / .NET), 33 bytes
^((.)(?=.*
(?=(\4?))(\3.*?\2)))*
Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - Python import regex
Try it online! - Ruby
Try it online! - .NET
Copies the capture back and forth between \3
and \4
to avoid use of nested backreferences, adding Python and Ruby support (and as the lookahead is atomic, it's also another way of adding .NET support).
\$\large\textit{Anonymous functions}\$
Julia, 52 51 50 bytes
-1 byte thanks to MarcMush
-1 byte thanks to MarcMush
x->y->count(r"^((.)(?*.*
(\3?+.*\2)))*
",x*'
'y)>0
Attempt This Online!
Yep, Julia string literals can contain an unescaped raw newline!
Beats Simeon Schaub's answer by 2 bytes when both are converted to the same type of declaration, e.g. currying, as used here.
Of course, both could also be 2 bytes shorter with operator overloading.
anna
is a subsequence (but not a substring) ofbanana
. String X is a subsequence of string Y just if X can be obtained from Y by deleting zero or more of the elements of Y; e.g., deleting theb
and the seconda
frombanana
givesanna
. \$\endgroup\$