Pyth, 16 bytes
u|pH<GJxGH>GJwz
Try it online: Demonstration
This is quite hacky. Stack-based languages might have an advantage here.
Explanation
implicit: z = 1st input line, w = 2nd
u wz reduce, start with G = z
for each H in w, update G to:
xGH index of H in G
h +1
J store in J
<GJ substring: G[:J] (everything before index J)
pH print substring thanthen H (without newlines)
| afterwards (actually or, but p always returns 0)
>GJ substring: G[J:] (everything from index J to end)
update G with ^
afterwards implicitly print the remainder G