Site search - how to detect concatenated words ie redshoe

[Hippocrates]

I want to make my site search more intelligent.
I notice that Google can detect that if I search the term "yellowshoes" Google asks me: Did you mean "yellow shoes"

How is something likes this done query-wise?
Should one perhaps cycle through the term to extract for example:

ye llowshoes
yel lowshoes
yell owshoes
yello wshoes
yellow shoes
yellows hoes
yellowsh oes
yellowsho es

and query them all to see which get the most hits or maybe query against previous queries to see what others searched for?
Any ideas?