[Question]
  [
Here’s how to **backspace-and-retype** from one string to another:
1. Start from the first string.
2. Remove characters at the end until the result is a **prefix** of the second string. (This may take 0 steps.)
3. Add characters at the end until the result equals the second string. (This may take 0 steps, too.)
For example, the path from `fooabc` to `fooxyz` looks like:
```
fooabc
fooab
fooa
foo
foox
fooxy
fooxyz
```
## Task
Given a list of words, write a program that **backspace-and-retypes** its way from the empty string, to all of the words in the list in succession, back to the empty string. Output all intermediate strings.
For example, given the input list `["abc", "abd", "aefg", "h"]`, the output should be:
```
a
ab
abc
ab
abd
ab
a
ae
aef
aefg
aef
ae
a
h
```
## Rules
You may return or print a list of strings, or a single string with some delimiter of choice. You may **optionally** include the initial and final empty strings. The input is guaranteed to contain at least one word, and each word is guaranteed to contain only lowercase ASCII letters (`a`–`z`). *Edit:* consecutive strings in the input are guaranteed not to equal each other.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"); shortest code in bytes wins.
A reference implementation in Python 3: [Try it online!](https://tio.run/nexus/python3#hY3BDsIgDIbve4q6y5jiEnZc4pMQYtAxR4JAoEriy09YlsWbvfzt/39tF/30LiDIiFVyYYxwKX1nNKogzVW9pSHa@heStt0J3jQUjutEoWlENbkAiVFIPWgLH@3JFq7C2SDaoYJcadZGgXWY0S6iDBiTxpkktgGlfNAWi7U7ieWvifHhzMTPnWwfst//WT0VhhtlSyCWhdfydq8pZBlXUdOj6FyLLw "Python 3 – TIO Nexus\"")
  
[Answer]
## Perl, 43 bytes
42 bytes of code + `-n` flags.
```
chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge
```
To run it:
```
perl -nE 'chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge' <<< "abc
abd
aefg
h"
```
[Answer]
# Pyth, ~~25~~ 23 bytes
```
V+QkWxNk
=Pk)
M>._Nl~kN
```
[Try it online.](http://pyth.herokuapp.com/?code=V%2BQkWxNk%0A%3DPk%29%0AM%3E._Nl%7EkN&input=%5B%22abc%22%2C+%22abd%22%2C+%22aefg%22%2C+%22h%22%5D&debug=0)
[Answer]
# Java 8, 144 bytes
This one is similar to the reference implementation but combines the two `while` loops. It's a lambda expression accepting a `String[]` parameter.
```
a->{String c="";int l=0,i;for(String w:a)while((i=w.indexOf(c))!=0||!c.equals(w))System.out.println(c=i!=0?c.substring(0,--l):c+w.charAt(l++));}
```
## Ungolfed
```
a -> {
    String c = "";
    int l = 0, i;
    for (String w : a)
        while ((i = w.indexOf(c)) != 0 || !c.equals(w))
            System.out.println(c = i != 0 ? c.substring(0, --l) : c + w.charAt(l++));
}
```
## Acknowledgments
* -38 bytes thanks to CAD97's lambda suggestion
[Answer]
# Mathematica, 149 bytes
```
Reap[Fold[n=NestWhile;s=StringMatchQ;r=StringReplace;n[k=#2;Sow@r[k,#~~a_~~___:>#<>a]&,n[Sow@r[#,a___~~_:>a]&,#,!s[k,#~~___]&],k!=#&]&,"",#]][[2,1]]&
```
[Answer]
## [Retina](https://github.com/m-ender/retina), 39 bytes
Byte count assumes ISO 8859-1 encoding.
```
M!&r`.+
%)`\G.
¶$`$&
+`((.*).¶)\2¶\1
$1
```
[Try it online!](https://tio.run/nexus/retina#@@@rqFaUoKfNpaqZEOOux3Vom0qCihqXdoKGhp6Wpt6hbZoxRoe2xRhyqRj@/5@YlMyVmJTClZials6VAQA "Retina – TIO Nexus")
Input and output are linefeed-separated lists. Output does include the leading and trailing empty string.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~31~~ ~~29~~ 26 bytes
```
⁷œ|;\
ÇṚðfḢṭḟ;ḟ@ḊðÇ}
⁷;ç2\
```
[Try it online!](https://tio.run/nexus/jelly#@/@ocfvRyTXWMVyH2x/unHV4Q9rDHYse7lz7cMd8ayB2eLij6/CGw@21XEB11oeXG8X8//9fPTEpWV1HAUilgKnUtHQQnaEOAA "Jelly – TIO Nexus")
### How it works
```
⁷;ç2\           Main link. Argument: A (string array)
⁷;              Prepend a linefeed to A. 
                This is cheaper than prepending an empty string.
  ç2\           Reduce all overlapping pairs by the second helper link.
ÇṚðfḢṭḟ;ḟ@ḊðÇ}  Second helper link. Arguments: s, t (strings)
Ç               Call the first helper link with argument s.
 Ṛ              Reverse the results.
            Ç}  Call the first helper link with argument t.
  ð        ð    Combine everything in between into a dyadic chain, and call it
                with the results to both sides as arguments.
                Let's call the arguments S and T.
   f            Filter; get the common strings of S and T.
    Ḣ           Head; select the first one.
      ḟ         Filterfalse; get the strings in S that do not appear in T.
     ṭ          Tack; append the left result to the right one.
        ḟ@      Filterfalse swap; get the strings in T that do not appear in S.
       ;        Concatenate the results to both sides.
          Ḋ     Dequeue; remove the first string.
⁷œ|;\           First helper link. Argument: s (string)
⁷œ|             Linefeed multiset union; prepend a linefeed to s unless it already
                has a linefeed in it (the first string does).
   ;\           Concatenate cumulative reduce; generate all prefixes of the result.
```
[Answer]
# GNU M4, 228 or 232 bytes¹
(¹ depending on whether to end the file with `dnl\n` or not—I'm still new to both golfing and M4)
```
define(E,`ifelse(index($2,$1),0,`T($1,$2)',`$1
E(substr($1,0,decr(len($1))),$2)')')define(T,`ifelse($1,$2,,`$1
T(substr($2,0,incr(len($1))),$2)')')define(K,`ifelse($2,,$1,`E($1,$2)K(shift($@))')')define(M,`K(substr($1,0,1),$@)')
```
Additionally, 3 bytes could be saved by replacing the second argument for `substr` from `0` to the empty string, but that would produce a lot of warnings on stderr.
Ungolfed:
```
define(erase_til_prefix, `dnl arguments: src dst; prints src and chops one char off of it until src == dst, at which point it calls type_til_complete instead
ifelse(dnl
index($2, $1), 0, `type_til_complete($1, $2)',dnl
`$1
erase_til_prefix(substr($1, 0, decr(len($1))), $2)dnl
')')dnl
define(type_til_complete, `dnl arguments: src dst; types src, does not type `dst' itself
ifelse(dnl
$1, $2, ,dnl
`$1
type_til_complete(substr($2, 0, incr(len($1))), $2)'dnl
)')dnl
define(main_, `dnl
ifelse(dnl
$2, , $1, dnl no arguments left
`erase_til_prefix($1, $2)main_(shift($@))'dnl
)')dnl
define(main, `main_(substr($1, 0, 1), $@)')dnl
```
Usage:
```
$ m4 <<<"include(\`backspace-golfed.m4')M(abc, abd, aefg, abcdefg, h)"
```
[Answer]
## [Haskell](https://www.haskell.org/), ~~102 93 91~~ 90 bytes
```
(?)=take.length
a!x@(b:c)|a==b=b!c|a/=a?b=a:init a!x|d<-'?':a=a:d?b!x
_!x=x
(""!).(++[""])
```
The last line is an anonymous function, which takes and returns a list of strings.
[Try it online!](https://tio.run/nexus/haskell#XYrLCsIwEADv/YrNIjShWu/BJf5HKbJ5EIM2iOSQQ/49FjwIXgZmmI1TBoLXO@UCB4iwIHuPR2TrvvThZ3997dIoKvwI8zPkWO4Di3qVVjvVmMiSFa7xmdhYYp1yKrAPzV9Ooxk1780bK@pwE5XqEEkiCjXLaVoQV9X7Bw "Haskell – TIO Nexus")
## Explanation
My solution is recursive.
First, `?` is a helper infix function: `a?b` gives the first `length a` characters of `b`, or the whole of `b` if `a` is longer.
Next I define an infix function `!`.
The idea is that `a!x`, where `a` is a string and `x` a list of strings, produces the path from `a` to the first string in `x` and recurses to the tail of `x`.
On the final line I define an anonymous function that appends the empty string, then applies `!` to the empty string and the input.
Explanation of `!`:
```
a!x@(b:c)        -- a!x, where x has head b and tail c:
  |a==b          -- If a equals b,
    =b!c         -- recurse to x.
  |a/=a?b        -- If a is not a prefix of b,
    =a:          -- produce a and
    init a!x     -- continue with one shorter prefix of a.
  |              -- Otherwise a is a proper prefix of b.
   d<-'?':a      -- Let d be a with an extra dummy element,
    =a:          -- produce a and
    d?b!x        -- continue with one longer prefix of b.
_!x=x            -- If x is empty, return x.
```
[Answer]
# Python 2, ~~118~~ ~~107~~ ~~103~~ ~~97~~ ~~93~~ 92 bytes
```
s=''
for i in input()+[s]:
 while i.find(s):s=s[:-1];print s
 while i>s:s+=i[len(s)];print s
```
Input is given as `['abc', 'abcdef', 'abcfed']`, or as [`"abc", "abcdef", "abcfed"]`.
Revision 1: -11 bytes. Credit goes to @xnor for his post on Python golfing tips, and to @Lynn for finding the tip for me, and to me for being smart. Two changes were made: Instead of `not s.startswith(i)`, I used `s.find(i)`, and instead of `i!=s` I used `i>s`.
Revision 2: -4 bytes. Credit goes to me realizing I made a really dumb mistake. Instead of using single-tab and double-tab indentation, I used single-space and single-tab indentation.
Revision 3: -6 bytes. Credit goes to @mbomb007 for suggesting to put the whiles on a single line. I also fixed a bug by changing `s.find(i)` to `i.find(s)`.
Revision 4: -4 bytes. Credit goes to @xnor for realizing that I didn't need to store the input in a variable.
Revision 5: -1 byte. Credit goes to me for realizing that `['']` is the same thing as `[s]` when adding it to the input.
[Answer]
# PHP, ~~116~~ ~~111~~ ~~101~~ 83 bytes
Note: uses Windows-1252 encoding.
```
for(;$w=$argv[++$i];)for(;$c!=$w;)echo$c=($c^$c^$w)==$c?$c.ÿ&$w:substr($c,0,-1),~õ;
```
Run like this:
```
php -r 'for(;$w=$argv[++$i];)for(;$c!=$w;)echo$c=($c^$c^$w)==$c?$c.ÿ&$w:substr($c,0,-1),~õ;' -- abc abd aefg h 2>/dev/null
> a
> ab
> abc
> ab
> abd
> ab
> a
> ae
> aef
> aefg
> aef
> ae
> a
>
> h
```
# Explanation
```
for(                       # Outer loop.
  ;
  $w=$argv[++$i];          # Loops over the input words.
)
  for(                     # Second inner loop.
    ;
    $c!=$w;                # Loop until the word was output.
  )
    echo $c=
      ($c^$c^$w)==$c?      # Check if last output string is a substring
                           # match with the next word to output.
        $c.ÿ&$w:           # ... If yes, suffix the string with the next
                           # char of the word, and output the result.
        substr($c,0,-1),   # ... If not, remove a char and output.
      ~õ;                  # Output newline.
```
# Tweaks
* Saved 5 bytes by using `trim($c^$w,"\0")` to check for substring match instead of `$c&&strpos($w,$c)!==0`.
* Saved 2 bytes by using `~ÿ` to yield a string with a NUL byte instead of `"\0"`
* Saved 8 bytes by using `$c=$c.ÿ&$w` to suffix `$c` with the next char of `$w`
* Saved a massive 18 bytes by combining the logic of the 2 inner loops in a single loop
* Fixed a bug with a testcase from the comments, no change in byte count
[Answer]
## Batch, ~~296~~ 291 bytes
```
@echo off
set f=
set t=%1
:t
set f=%f%%t:~,1%
set t=%t:~1%
echo(%f%
if not "%t%"=="" goto t
shift
set t=%1
set s=%f%
set p=
:h
if %s:~,1%==%t:~,1% set p=%p%%t:~,1%&set s=%s:~1%&set t=%t:~1%&goto h
:b
set f=%f:~,-1%
echo(%f%
if not "%f%"=="%p%" goto b
if not "%1"=="" goto t
```
Computing the common prefix was cumbersome.
[Answer]
# [Pip](https://github.com/dloscutoff/pip), ~~33~~ 30 bytes
```
FsgAExTyQsYPyQs@<#y?y.s@#y;@<y
```
[Try it online!](https://tio.run/##K8gs@P/frTjd0bUipDKwODIASDjYKFfaV@oVOyhXWjvYVP7//z8xKRmIU/4npqal/88AAA "Pip – Try It Online")
### Explanation
```
                                g is list of cmdline args; x & y are "" (implicit)
Fs                              For each s in
  gAEx                          g with an empty string appended:
      TyQs                       Do this till y equals s:
              s@<                 Get the prefix of s
                 #y               having the same length as y
            yQ                    and check if it equals y
                   ?              If so (y is a prefix of s), calculate:
                    y.             y, concatenated with
                      s@           the character in s at index
                        #y         len(y)
                          ;       If not, calculate:
                           @<y     y without its last character
          YP                      Print that quantity and yank it back into y
```
[Answer]
# PHP, 153 bytes
awfully long :(
```
for($s=$argv[$k=1];$t=$argv[++$k];){for(;$s>""&&strstr($t,$s)!=$t;$s=substr($s,0,-1))echo"$s
";for($i=strlen($s);$s<$t;$s.=$t[$i++])echo"$s
";echo"$s
";}
```
Run with `php -nr '<ode>' <text1> <text2> ...`.
[Answer]
# JavaScript (ES6), 135 bytes
Interesting challenge! Usage: `g(["abc", "abd", "aefg", "h"])`. I couldn't seem to save any bytes by writing this as one function, so it's two. Newlines not included in byte count.
```
f=a=>console.log(([,...z]=[x,y]=a)[0])||
y?f(a=(x==y.slice(0,-1))?z:([y.match(x)
?x+y[x.length]:x.slice(0,-1),...z])):1;
g=a=>f(['',...a])
```
I'm sure this can be reduced a lot more. Will add ungolfed version later.
[Answer]
# Javascript, 98 bytes
```
a=>{c="",l=0;for(w of a)while((i=w.indexOf(c))!=0||c!=w)alert(c=i!=0?c.substring(0,--l):c+w[l++])}
```
Port of Jakob's Java answer
]