Haskell, 109 104 98 97 bytes
Probably not very good but Hopefully this will kick things off a bit.
a!s=[1]==[1|x<-s,and$zipWith(==)a x]
a#s=[x|x<-map(`take`a)[0..],x!s]!!0
f s=map(#s)s
f.map(++"$")
Explanation
We define a couple of functions here. The first (!) is a predicate that determines that there is exactly 1 string in a list starting with a substring.
After that we have (#) which will take a string and a list and determine the shortest substring of a particular string that returns true for our predicate (!).
We then define a function f that maps (#) to each item in a list with respects to that list. Our final function is just this, but we compose it with map(++"$") to get the $ behavior required.