insertspacesbetweenwords

Question

In this challenge, your input is a string of lower-case letters like this:

insertspacesbetweenwords

and a dictionary like the that from my other challenge. You may assume that the dictionary file contains only lower-case letters and line-feed characters. Furthermore, the last character in the dictionary file is a line-feed character and the entries are sorted alphabetically.

Write a function that given these two strings, returns a single string containing all possible ways to insert spaces between some of the characters in the input string, such that the words created are all in the dictionary. Each possibility shall be terminated with a line-feed character. Some lines of the output for the example are:

insert spaces between words
insert space s between words
insert spaces between word s
insert space s between word s
insert spaces be tween words

The order of the output lines doesn't matter.

This is codegolf, the usual scoring rules apply, standard loopholes are verboten.

Answer 1

Haskell, 113 107 105 88 87 86 bytes

Works for empty inputs too (but gives an empty string as output).

s!d=unlines[w|w<-map concat$mapM(\c->[[c],[' ',c]])s,all(`elem`lines d).words$w,w>"!"]

Defines an infix binary function !. Call it like this:

"abababbaab" ! "ab\nba\na\nbab\n"

Result:

"ab ab ab ba ab\nab a bab ba ab\na bab ab ba ab\na ba bab ba ab\n"

Explanation

The idea is to split the left input string s into words by inserting spaces in all possible ways, and keep those that consist of words of the dictionary d. A leading space is checked by comparing to the string "!".

s!d=                           -- Define the string s!d by
 unlines                       -- joining with line-breaks
  [w|w<-                       -- the strings w obtained by
    map concat$                -- concatenating each list of strings
    mapM(\c->[[c],[' ',c]])s,  -- obtained by replacing each letter 'c' of s by
                               -- either "c" or " c",
   all(`elem`lines d).         -- such that only lines of d
    words$w,                   -- occur as words in w, and
   w>"!"]                      -- w is lexicographically larger than "!",
                               -- which here means that w does not begin with a space.

Answer 2

Python 3, 88

f=lambda x,w,s=[]:[x or print(*s)]+[x.find(y)or f(x[len(y):],w,s+[y])for y in w.split()]

String to split is x, the dictionary string is w.

The idea is to repeatedly check which strings y of the dictionary are a prefix for the current string x. The expression x.find(y) evaluates to the Falsey 0 only if x starts with y (substrings not present give -1), so the short-circuiting of or makes the function recurse down only when the prefixes matches. The prefix is chopped off with x[len(y):] and the list of subwords is updated in s.

When the whole string x has been consumed, we print the subwords s, automatically joined by spaces.