AWK, 68 48 bytes

{for(;i++<split($1,b,X);)x=x b[i]".*";print$2~x}

Try it online!

{l=split($1,b,X);for(j=1;i++<split($2,a,X);)j+=a[i]~b[j];print(j>l)}

{for(;i++<split($1,b,X);) # convert search word to array 
x=x b[i]".*";             # compose regex with chars
print$2~x}                # print result of regex comparison

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 /}} Python^regex / 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!

Curries its arguments so it can be called directly as a lambda as-is. Beats Simeon Schaub's answer by 2 bytes when that is converted to currying (52 bytes).

\$\large\textit{Named functions}\$

Julia, 48 bytes

x\y=count(r"^((.)(?*.*
(\3?+.*\2)))*
",x*'
'y)>0

Used as a lambda: Attempt This Online
Used as an operator: Attempt This Online

Still 2 bytes shorter than Simeon Schaub's converted answer (50 bytes).

R, 40 bytes

\(x,y)!sum(attr(adist(x,y,,T),"c")[2:3])

Attempt This Online!

This solution is based upon Levenshtein distance. In this particular challenge, the task is to check whether the insertion of characters into the substring would result in the main string. (Or, in the same way, we can remove characters from the main string.)

Accordingly, applying the function adist to the input strings we are getting the number of insertions, deletions and substitutions. The only thing that remains is to output a TRUE if the number of substitutions and deletions are both 0 and FALSE otherwise.

Nekomata + -e, 2 bytes

S=

Attempt This Online!

S       Check if any subset of the first string
 =      is equal to the second string

Thunno 2 G, 2 bytes

ʠ=

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

ʠ=  # Implicit input
ʠ   # Powerset of the first input string
 =  # Vectorised equality check with the second input string
    # Check if any are true, and implicitly output

Python 3.8 (pre-release), 42 bytes

lambda a,b:''in[a:=a[a[:1]==c:]for c in b]

Try it online!

Python 3.8 (pre-release), 48 bytes

lambda a,b,j=0:all((j:=1+b.find(c,j))for c in a)

Try it online!

In Python 3.10+, we don't need parens around the walrus expression for 46 bytes.

Python 2, 48 bytes

lambda a,b:re.search('.*'.join(a),b)>0
import re

Try it online!

Copied from this answer of Lynn. The >0 can be omitted if just truthy/falsey output is OK.

Python 2, 49 bytes

def f(a,b):l=iter(b);print all(c in l for c in a)

Try it online!

A dazzling new method introduced to me by qwatry. The idea is that turning b into the iterator l will consume values whenever they are read. So, checking c in l will consume values left to right until it finds one that equals c or it reaches the end.

Python 2, 50 bytes

f=lambda a,b:b and f(a[a[:1]==b[0]:],b[1:])or''==a

Try it online!

Python 2, 50 bytes

lambda a,b:reduce(lambda s,c:s[c==s[:1]:],b,a)==''

Try it online!

Pyth, 5 bytes

}hQye

Explanation

}hQye
 hQ       The first input...
}         ... is an element of...
   y      ... the power set...
    eQ    ... of the second input.

K (ngn/k), 32 18 bytes

~#*{(=/*'x;1)_'x}/

Try it online!

Haskell + hgl, 2 bytes

iS

Attempt This Online!

So this is a builtin. There are actually a couple of builtins. There's also fiS which is the same function but the arguments flipped, there iSW eq which how iS is defined internally. There's fe<ss which gets all subsequences of y and checks if x is among them. There's ap eq<lSW which tests if the longest common subsequence is equal to the second element.

But these are no fun. Let's have a true no builtins solution

Regex based, 17 bytes

pP<rXx<ic".*"<m p

Also

pP<rXx<ic".*"<!<p

This works like all the other regex answers here. It adds .* between items and then matches a regex.

Parser based, 15 bytes

pP<mF(aK h'<χ)

This works similarly to the regex answer. It replace every character in the string with a parser that matches anything ending in that character. It then sequences all the parsers and checks if there is any partial matches.

It's cheaper than the regex which is a little surprising.

Reflections

The regex answer is the one with the most room for improvement.

• There should be functions that build and apply regexes all in one. It's silly to have to build and then apply the regex separately. This would save 3 bytes on the regex solution
• Hard to imagine a situation in which <!< is going to be useful. Here we can see it's not saving anything. Maybe this should be shortened, the docs should have some info about when it is useful.
• There should be more versions of ic and is. Some that add copies to the outside, and a versions that are mapped with pure like the regex answer.

With the above changes the regex answer could look like

pPX<icp".*"

The only other suggestion I have is that maybe aK h' should get a synonym. It's basically "ends with", which seems like a concept that might come up again.

brev, 78 bytes

(define(s(x . xs)y)(aif(memq x y)(s xs(cdr it))#f))(define(s'()y)#t)

68 to define s, but you've got to call it as (as-list s) to handle string input.

(define (s (x . xs) y)
  (aif (memq x y) (s xs (cdr it)) #f))

(define (s '() y) #t)

(map (fn (apply (as-list s) x))
     '((""     "z00")
       ("z00"  "z00")
       ("z00"  "00z0")
       ("aa"   "anna")
       ("anna" "banana")
       ("Anna" "banana")))

Bonus! Regex version 50 bytes:

(fn(with(strse x"."(conc(m 0)".*"))(strse? y it)))

JavaScript (no regex), 45 bytes

y=>x=>(i=0,[...y].map(c=>c==x[i]&&i++),!x[i])

Should be called like

f(haystack)(needle)

Factor + math.combinatorics, 19 bytes

[ all-subsets in? ]

Try it online!

Charcoal, 18 17 bytes

ＦηＦ⁼ι∧θ§θ⁰≔Φθμθ¬θ

Try it online! Link is to verbose version of code. Uses Charcoal's default Boolean output of - for true, nothing for false. Explanation:

Ｆη

Loop over the characters of Y.

Ｆ⁼ι∧θ§θ⁰

See if this character is the next character of X.

≔Φθμθ

If so then remove that character from X.

¬θ

Were all the characters of X consumed?

Vyxal, 2 bytes

ṗc

Try it Online!

Python, 45 bytes

lambda a,b:{1,l:=iter(b)}>{c in l for c in a}

Attempt This Online!

Builds on @qwatry's method used in @xnor's answer: iter consumes elements as they are searched for, so c in l "uses up" the character if it is found.

Some trickery lets us combine the all and the iterator assignment:

• {c in l for c in a} is a set comprehension which effectively deduplicates its contents, so it's always one of {}, {False}, {True}, or {False, True}
• 1 and 0 are equivalent to True and False
• The > operator tests if {True, iter(b)} is a strict superset of the result, which is true only if that result is {} or {True}, i.e. all the c in l expressions were true
• By including l:=iter(b) in the set, we can sequence the evaluation order correctly with minimal parentheses by reusing the set's {} grouping
• It also lets us use > instead of >= because the iterator will never be present in the boolean set
• Otherwise, >= would be necessary because {True} is not a strict superset of {True}

Vyxal, 6 bytes

ṗƛṅ;$c

Try it Online!

MMIX, 40 bytes (10 instrs)

C strings.

00000000: 8302 0000 8303 0100 dc04 0203 30FF 0203  ............0...
00000010: 73FF FF01 2200 00FF 2301 0101 5b04 fff9  s..."...#...[...
00000020: 7300 0201 f801 0000                      s.......

Disassembly

subseq  LDBU $2,$0,0        // loop: av = *a
        LDBU $3,$1,0        // bv = *v
        MOR  $4,$2,$3       // t0 = av && bv (MOR is faster than MUL)
        CMP  $255,$2,$3     // t1 = av <=> bv
        ZSZ  $255,$255,1    // t1 = !t1
        ADDU $0,$0,$255     // a += t1
        ADDU $1,$1,1        // b += 1
        PBNZ $4,subseq      // iflikely(t0) goto loop
        ZSZ  $0,$2,1        // a = !t0
        POP  1,0            // return a

Obvious algorithm, with only one branch!

For wchar_t, replace LDBU with LDWU (and similarly for codepoint_t); additionally, replace ADDU $0,$0,$255 with 2ADDU $0,$255,$0 (4ADDU for codepoints), and ADDU $1,$1,1 with ADDU $1,$1,2 or ADDU $1,$1,4.

Lua, 85 68 66 bytes

_,b=...for c in (...):gmatch"."do b=b:gsub(c,"",1)end print(b=="")

Try it online!

Explanation

... is the variable argument operator, it returns all remaining arguments to the current function (the top-level block in this case). We can force it to return just one variable by encasing it in parentheses.

gmatch() is a pattern-matching function which returns an iterator function, we use it to loop over every character in the input string.

gsub() is a substitution function, we use it to clear matched characters from the subset contender. The extra parameter is the number of substitutions to make, 1 in this case.

x86-16 machine code, 12 10 bytes

Binary:

00000000: 41ac f2ae e303 4a75 f8c3                 A.....Ju..

Unassembled listing:

41          INC  CX                 ; Loop counter is 1 greater than string length 
        SCAN_LOOP: 
AC          LODSB                   ; load next char of acronym into AL 
F2 AE       REPNZ SCASB             ; search until char AL is found 
E3 03       JCXZ DONE               ; stop if end of first string reached 
4A          DEC  DX                 ; decrement second string counter 
75 F8       JNZ  SCAN_LOOP          ; stop if end of second string reached 
        DONE: 
C3          RET                     ; return to caller

Callable function. Input: Y string pointer in SI, length in CX. X string pointer in DI, length in DX. Output is ZF if Truthy.

Example test program:

This test program uses additional PC DOS API I/O routines to take multi-line input from STDIN.

Java 8, 163 162 38 35 bytes

a->b->b.matches(a.replace("",".*"))

-124 bytes by converting to Java 8, and pasting my answer from the duplicated challenge.

NOTE: Doesn't work if the input contains special regex-characters, but this would invalidate a lot of existing answers as well.

Try it online.

Explanation:

a->b->         // Method with two String parameters and boolean return-type
  b.matches(   //  Check if the second input matches the regex:
   a           //   The first input,
    .replace("",".*"))
               //   where every character is surrounded with ".*"

For example:

a="anna"
b="banana"

Will do the check:

"banana".matches("^.*a.*n.*n.*a.*$")

Zsh -o glob_subst, 14 bytes

>:$1>${2///*}*

Try it online!

Explanation:

• >:$1: copy stdin to a file named : and the first argument. The colon ensures that we don't try to create a file with an empty name in the case of an empty string as input. Since we don't take any input from stdin, this just creates an empty file.
• >${2///*}*: try to copy stdin (again) to a file that matches the pattern resulting from the expansion of ${2///*}* If no such file exists, an error will occur. The -o glob_subst ensures that the expanded value is treated as a pattern. Otherwise, it will be treated as a literal string. Alternatively, this option can be removed and ${~2///*}* used instead for +1 byte.
  • ${2}: take the second argument
  • ///*: replace every empty string with an asterisk; this results in abc -> *a*b*c
  • append another asterisk. Asterisks simply mean "match any sequence

Husk, 2 bytes

€Ṗ

Try it online!

Having a single byte builtin for powerset is useful.

Pyth, 5 bytes

}hQye

Try it online!

Pyth   | Explanation
-------+------------------------------------------
}hQye  | Full code
}hQyeQ | "       " with implicit variables
-------+------------------------------------------
}      | return whether arg0 is an element of arg1
 hQ    |  first element of input
   y   |  powerset of
    eQ |   last element of input

Jelly, 3 bytes

ŒPi

Try it online!

Outputs 0 for false and a non-negative integer for true

How it works

ŒPi - Main link. Takes X on the left and Y on the right
ŒP  - Powerset of X
  i - Index of y, or 0

05AB1E, 3 bytes

æQà

Try it online or verify all test cases.

Or alternatively:

æså

Try it online or verify all test cases.

With both programs the first input is \$Y\$ and the second input is \$X\$.

Explanation:

æ    # Get the powerset of the (implicit) input-string `Y`
 Q   # Check for each if it's equal to the (implicit) input-String `X`
  à  # And check if any are truthy by taking the maximum
     # (after which this result is output implicitly)

æ    # Get the powerset of the (implicit) input-String `Y`
 s   # Swap to take the (implicit) input-String `X`
     # (could also be `I` or `²` to simply take input)
  å  # Check if this string is in the powerset-list of strings
     # (after which this result is output implicitly)

Perl 6, 34 28 bytes

-6 bytes thanks to nwellnhof

{$!=S:g/<(/.*/;&{?/<{$!}>/}}

Try it online!

Anonymous code block that takes input curried, like f(X)(Y). This does the familiar join by .* and evaluate as a regex as other answers, but takes a couple of shortcuts.

Explanation:

{                          }  # Anonymous code block
 $!=            # Assign to $!
    S:g/<(/.*/  # Inserting .* between every character
              ;&{         }   # And return an anonymous code block
                 ?/      /    # That returns if the input matches
                   <{$!}>     # The $! regex

JavaScript, 32 bytes

Repost of a port of Kevin's Java solution to a duplicate challenge, modified in case my choices for I/O weren't standards at the time this challenge was posted.

x=>y=>!!y.match([...x].join`.*`)

Try it online! (will update with this challenge's test cases when I get back to a computer)

Julia 1.0, 53 bytes

f(x,y)=(x==""||[x=x[2:end] for c=y if c==x[1]];x=="")

Try it online!

Haskell, 36 bytes

(a:b)%(c:d)=([a|a/=c]++b)%d
s%t=s<=t

Try it online!

37 bytes

(.map concat.mapM(\c->["",[c]])).elem

Try it online!

I think mapM postdates this challenge. If we can assume the characters are printable, we can do

36 bytes

(.map(filter(>' ')).mapM(:" ")).elem

Try it online!

37 bytes

(null.).foldr(?)
c?(h:t)|c==h=t
c?s=s

Try it online!

Red, 82 bytes

func[x y][parse/case y collect[foreach c x[keep reduce['to c 'skip]]keep[to end]]]

Try it online!

Japt, 4 bytes

Repost from a duplicate challenge.

Takes input in reverse order (Y, then X).

à øV

Try it

APL(NARS), chars 46, bytes 92

{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}

test:

  h←{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}
  '' h 'z00'
1
  'z00' h 'z00'
1
  'z00' h '00z0'
0
  'aa' h 'anna'
1
  'anna' h 'banana'
1
  'Anna' h 'banana'
0

comment:

{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}
 ⍳¯1+2*k←≢w←⍵    this assign to w the argument and k argument lenght, it return 1..(2^k)-1 range
 {⍵⊤⍨k⍴2}¨      for each element of 1..(2^k)-1 convert in base 2 with lenght k (as the arg lenght)
 {⍵⊂w}¨         use the binary array above calculation for all partition argument
 ,/¨            concatenate each element of partition
 ↑¨             get the firs element of each element because they are all enclosed
 (⊂''),         add to the array the element (⊂'')
 (⊂,⍺)∊         see if (⊂,⍺) is one element of the array, and return 1 true o 0 false

How all you can see the comments are +- superfluous all is easy...

I have to say not understand why the last instruction is not "(,⍺)∊" in the place of "(⊂,⍺)∊" because for example in code

  q←{↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}
  o q '123'
┌7──────────────────────────────────────┐
│┌1─┐ ┌1─┐ ┌2──┐ ┌1─┐ ┌2──┐ ┌2──┐ ┌3───┐│
││ 3│ │ 2│ │ 23│ │ 1│ │ 13│ │ 12│ │ 123││
│└──┘ └──┘ └───┘ └──┘ └───┘ └───┘ └────┘2
└∊──────────────────────────────────────┘
  o (,'3')
┌1─┐
│ 3│
└──┘

all you see array of 1 element (,'3') is the element of the set of instruction q '123', but

  o (,'3')∊q '123'
┌1─┐
│ 0│
└~─┘

return one array of unclosed 0 instead of number 1... for workaround that one has to write:

  o (⊂,'3')∊q '123'
1
~

that is the right result even if the element seems different because :

  o (⊂,'3')
┌────┐
│┌1─┐│
││ 3││
│└──┘2
└∊───┘

It is sure i make some error because i am not so smart... where is my error?

Brachylog, 2 bytes

⊆ᵈ

Try it online!

As with this answer, ⊆ is a built-in predicate that declares a relationship between the input and output variables, and ᵈ is a meta-predicate that modifies it to declare that same relationship between the first and second elements of the input variable instead (and unify the output variable with the second element but as this is a decision problem that doesn't end up mattering here). X⊆Y is an assertion that X is a subsequence of Y, therefore so is [X,Y]⊆ᵈ.

This predicate (which of course outputs through success or failure which prints true. or false. when it's run as a program) takes input as a list of two strings. If input is a bit more flexible...

Brachylog, 1 byte

⊆

Try it online!

Takes string X as the input variable and string Y as the output variable. Outputs through success or failure, as before. If run as a full program, X is supplied as the input and Y is supplied as the first command line argument.

Python 2, 47 bytes

x,y=map(list,input())
while x:y.remove(x.pop())

Try it online!

Takes two quote-delimited strings via STDIN as input.

Output is by presence or absence of an error, which is allowed per meta consensus.

Explanation:

             # get arguments from STDIN
             input()
    # convert each argument to a list
    map(list,.......)
# split arguments into two variables
x,y=..................

# while x still has elements
while x:
                 # remove the final element of x and return its value
                 x.pop()
        # remove the first matching item in y
        # this will error if there is no matching element
        y.remove(.......)

# if the loop is exited without error, all elements in x were in y

APL (Dyalog Unicode), 18 bytes^SBCS

Full program. Prompts for Y then for X.

×≢(∊'.*'∘,¨⍞)⎕S⍬⊢⍞

Try it online!

⍞ prompt (for Y)

⊢ yield that (separates ⍬ from it)

(…)⎕S⍬ search for occurrences of the following, yielding one empty list for each match:

 ⍞ prompt (for X)

 '.*'∘,¨ prepend .* to each character

 ∊ ϵnlist (flatten)

≢ tally the number of matches

× sign of that

Perl 5, 17 bytes (+1?), full program

s//.*/g;$_=<>=~$_

Try it online!

Invoke with the p flag to the perl interpreter, as in perl -pe 's//.*/g;$_=<>=~$_'. Per the established scoring rules when this challenge was originally posted, this flag costs one extra byte. Under more recent rules, AFAICT, it may be free.

Either way, the input strings should be supplied on separate newline-terminated lines on stdin. Output (to stdout) will be 1 if the first input string is a substring of the second, or nothing at all if it's not.

Note that both input lines must have a newline at the end, or the program won't work correctly. Alternatively, you can add the l command line flag to the invocation to make perl strip the newlines; depending on the scoring rules in effect, this may or may not cost one extra byte. Note that using this flag will also append a newline to the output.

Original version (snippet, 18 bytes / chars)

$x=~s//.*/g,$y=~$x

Input is given in the variables $x and $y, result is the value of the expression (in scalar context). Note that $x is modified in the process. (Yes, I know using $_ instead of $x would let me save four chars, but doing that in a snippet that feels a bit too cheesy for me.)

How does it work?

The first part, $x=~s//.*/g, inserts the string .* between each character in $x. The second part, $y=~$x, treats $x as a regexp and matches $y against it. In Perl regexps, .* matches zero or more arbitrary characters, while all alphanumeric characters conveniently match themselves.

Swift, 27

print(Y.range(of:X) != nil)

PHP, 41 Bytes

prints 1 for true and nothing for false

<?=!levenshtein($argv[1],$argv[2],0,1,1);

If only insertions from word 1 to word 2 done the count is zero for true cases

levenshtein

Try it online!

PHP, 57 Bytes

prints 1 for true and 0 for false

Creates a Regex

<?=preg_match(_.chunk_split($argv[1],1,".*")._,$argv[2]);

Try it online!

PHP, 75 65 64 bytes

for(;$p=@strpos(_.$argv[2],$c=$argv[1][$i++],$p+1););echo""==$c;

takes input from command line arguments; prints 1 for true, empty string for false. Run with -r.

explanation:

• strpos returns false if needle $c is not in the haystack $argv[2] (after position $p),
  causing the loop to break.
• strpos also returns false for an empty needle, breaking the loop at the end of $argv[1].
• If $argv[1] is a subsequence of $argv[2], $c will be empty when the loop breaks.
• strpos needs @ to suppress Empty needle warning.

REXX, 76 bytes

o=1
do while x>''
  parse var x a+1 x
  parse var y(a)b+1 y
  o=o&a=b
  end
return o

Note that x and y are consumed by this routine. Readability is impaired by skipping a lot of whitespace and parentheses.

JavaScript (ES6), 42 bytes

Takes input n (needle) and h (haystack) in currying syntax (n)(h).

n=>h=>!!RegExp(n.split``.join`.*`).exec(h)

Test

let f =

n=>h=>!!RegExp(n.split``.join`.*`).exec(h)

console.log(f(''    )('z00'   )); // true
console.log(f('z00' )('z00'   )); // true 
console.log(f('z00' )('00z0'  )); // false
console.log(f('aa'  )('anna'  )); // true
console.log(f('anna')('banana')); // true
console.log(f('Anna')('banana')); // false

Python (75 52)

s=lambda a,b:a==''or b>''and s(a[a[0]==b[0]:],b[1:])

Simple recursive solution. First time golfing, so any tips on whittling this down are much appreciated :)

Tested with the following:

assert s('anna', 'banana') == True
assert s('oo0', 'oFopp0') == True
assert s 'this', 'this is a string') == True
assert s('that', 'this hat is large') == True
assert s('cba', 'abcdefg') == False

Thanks to @lirtosiast for some clever boolean tricks.

Retina, 26 bytes (not competing)

The language is newer than the challenge. Byte count assumes ISO 8859-1 encoding. Input is taken on two lines with Y first.

+`^(.)(.*¶)(?(\1).|)
$2
¶$

Try it online

Python (72)

import itertools as I;any(tuple(X)==Z for Z in I.permutations(Y,len(X)))

SWI-Prolog, SICStus

The built-in predicate sublist/2 of SICStus checks whether all the items in the first list also appear in the second list. This predicate is also available in SWI-Prolog via compatibility library, which can be loaded by the query [library(dialect/sicstus/lists)]..

Sample run:

25 ?- sublist("","z00").
true.

26 ?- sublist("z00","z00").
true .

27 ?- sublist("z00","00z0").
false.

28 ?- sublist("aa","anna").
true .

29 ?- sublist("anna","banana").
true .

30 ?- sublist("Anna","banana").
false.

The byte count can technically be 0, since all we are doing here is querying, much like how we run a program and supply input to it.

Python - 72

def f(a,b):
 c=len(a)
 for i in b:a=a.replace(i,"",1)
 print len(a+b)==c

J (20 chars)

(<x)e.(#:i.2^#y)<@#y

The input is given in the variables x and y. It makes a list of all subsequences of y, so don't use it for very big strings.

C, 23:

while(*y)*x-*y++?0:x++;

result in *x

http://ideone.com/BpITZ

Mathematica 19 17 27

LongestCommonSequence returns the longest non-contiguous subsequence of two strings. (Not to be confused with LongestCommonSubsequence, which returns the longest contiguous subsequence.

The following checks whether the longest contiguous subsequence is the first of the two strings. (So you must enter the shorter string followed by the larger string.)

LongestCommonSequence@##==#& 

Examples

LongestCommonSequence@## == # &["", "z00"]
LongestCommonSequence@## == # &["z00", "z00"]
LongestCommonSequence@## == # &["anna", "banana"]
LongestCommonSequence@## == # &["Anna", "banana"]

True True True False

The critical test is the third one, because "anna" is contained non contiguously in "banana".

Javascript, 104 chars

function _(x,y){f=true;for(c in x){if(y.indexOf(x[c])>-1)y=y.replace(x[c],"");else{f=!f;break}}return f}

Ungolfed

function _(x,y){
f=true;
    for(c in x)
    {
        if(y.indexOf(x[c])>-1)
           y=y.replace(x[c],"");
        else {
            f=!f;
            break;
        }
    }
    return f;
}

Python 132

Similar to Daniero's. Not the easiest solution, but it was fun to try. I'm new to Python, so I'm sure I could make it shorter if I knew a little bit more.

def f(i):
    s=x;j=0
    while j<len(s):t=~i%2;s=[s[:j]+s[j+1:],s][t];j+=t;i>>=1
    return s==y
print True in map(f,range(1,2**len(x)))

APL (31)

String handling is a bit lacking in APL.

{(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N}

usage:

      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} 'anna' 'banana'
1
      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} 'Anna' 'banana'
0
      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} '' 'banana'
1

Ruby 32 30 28

f=->a,b{b.match a.tr'','.*'}

This will return MatchData instance if a is subsequence of b or nil otherwise.

Old version that find substring instead of subsequence

Ruby 15

f=->a,b{!!b[a]}

Using String#[](str) method that returns str if str is a substring of self and !! to return Boolean if returned value can be usable as boolean (and don't need to be true or false) then it can be only 13 chars:

f=->a,b{b[a]}

It will return nil if a is not a substring of b.

Burlesque (6 chars)

6 chars in Burlesque: R@\/~[ (assuming x and y are on the stack. See here in action.)

Python, 66 62 59 58 chars

Kind of a fun solution, definitely a neat problem.

def f(n,h,r=0):
 for c in h:r+=n[r:r+1]==c
 return r==len(n)

C - 74 71 64

This doesn't beat Peter Taylor's solution, but I think it's pretty fun (plus, this is a complete working program, not just a function)

main(int c,char**v){for(;*v[1]!=0;++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(int c,char**v){for(;*v[1];++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(c,v)char**v;{while(*v[1])v[2]+=*v[1]++==*v[2];return*v[2];}

And ungolfed:

main(int argc, char** argv){
   char * input = argv[1];
   char * test  = argv[2];

   // advance through the input string. Each time the current input
   // character is equal to the current test character, increment
   // the position in the test string.

   for(; *input!='\0'; ++input) test += *input == *test;

   // return the character that we got to in the test string.
   // if it is '\0' then we got to the end of the test string which
   // means that it is a subsequence, and the 0 (EXIT_SUCCESS) value is returned
   // otherwise something non-zero is returned, indicating failure.
   return *test;
}

To test it you can do something like:

./is_subsequence banana anna && echo "yes" || echo "nope"    
# yes
./is_subsequence banana foobar && echo "yes" || echo "nope"    
# nope

A sort of anti-solution generating all subsequences of Y:

Python 93

l=len(y)
print x in[''.join(c for i,c in zip(bin(n)[2:].rjust(l,'0'),y)if i=='1')for n in range(2**l)]

PowerShell, 38

$args[1]-clike($args[0]-replace'','*')

Of course, any such regex- or pattern-matching-based solution has severe performance problems with longer strings. But since shortness is the criterion ...

C #, 70 113 107 90 characters

static bool S(string x,string y){return y.Any(c=>x==""||(x=x.Remove(0,c==x[0]?1:0))=="");}

CoffeeScript 73

Here's an alternative CoffeeScript answer, using regexes instead of recursion:

z=(x,y)->a='.*';a+=c+'.*'for c in x;b=eval('/'+a+'/');(y.replace b,'')<y

If the haystack matches a very greedy regex constructed from the needle, it will be replaced with an empty string. If the haystack is shorter than it started, the needle was a subsequence.

Returns false when x and y are both empty strings. Think we need a philosopher to tell us if an empty string is a subsequence of itself!

(Posted as a separate answer from my previous because it feels different enough to justify it).

CoffeeScript 112 100 95 89

My first attempt at code golf... hope I don't shame my family!

z=(x,y)->a=x.length;return 1if!a;b=y.indexOf x[0];return 0if!++b;z x[1..a],y[b..y.length]

Edit: turns out Coffeescript is more forgiving than I thought with whitespace.

Thanks to r.e.s. and Peter Taylor for some tips for making it a bit sleeker

C (52 chars)

s(char*x,char*y){return!*x||*y&&s(*x-*y?x:x+1,y+1);}

Test cases

Haskell, 51 37

h@(f:l)%(g:m)=f==g&&l%m||h%m;x%y=x<=y

Thanks to Hammar for the substantial improvement. It's now an infix function, but there seems to be no reason why it shouldn't.

Demonstration:

GHCi> :{
GHCi| zipWith (%) [""   , "z00", "z00" , "anna"  , "Anna"]
GHCi|             ["z00", "z00", "00z0", "banana", "banana"]
GHCi| :}
[True,True,False,True,False]

Ruby, 32 characters

s=->x,y{y=~/#{[*x.chars]*".*"}/}

This solution returns nil if x isn't a subsequence of y and a number otherwise (i.e. ruby equivalents to false and true). Examples:

p s['','z00']        # => 0   (i.e. true)
p s['z00','z00']     # => 0   (i.e. true)
p s['z00','00z0']    # => nil (i.e. false)
p s['anna','banana'] # => 1   (i.e. true)
p s['Anna','banana'] # => nil (i.e. false)

C, 120

main(i,c){char x[99],y[99];c=0;gets(y),gets(x);for(i=0;y[i]!='\0';)c+=y[i++]==x[c]?1:0;puts(x[c]=='\0'?"True":"False");}

Python (48 chars)

import re;s=lambda x,y:re.search('.*'.join(x),y)

Same approach as Howard's Ruby answer. Too bad about Python's need to import the regex package and its "verbose" lambda. :-)

GolfScript (22 chars)

X[0]+Y{1$(@={\}*;}/0=!

Assumes that input is taken as two predefined variables X and Y, although that is rather unusual in GolfScript. Leaves 1 for true or 0 for false on the stack.

Scala 106:

def m(a:String,b:String):Boolean=(a.size==0)||((b.size!=0)&&((a(0)==b(0)&&m(a.tail,b.tail))||m(a,b.tail)))

Python, 59 characters

def s(x,y):
 for c in y:
  if x:x=x[c==x[0]:]
 return x==""

I figured my answer would be better expressed in Python.

Edit: Added r.e.s.'s suggestions.

PHP, 90 characters

<?function s($x,$y){while($a<strlen($y))if($y[$a++]==$x[0])$x=substr($x,1);return $x=="";}