微软谷歌的一道面试题：如何分隔没有空格标点的英文句子

给你一个没有间隔的字符串“thisisasentence”，如何将他分割成如下的句子：“this is a sentence”。
提供一个函数用来检验一个字符串是不是单词：bool dic(char* w)；
完成下列的函数。要求效率尽可能快。
bool Detect(char* str)
{

}

尽量写出完整思路，最好有伪代码。

面试官提示：回溯，递归。我没想出来。还要考虑一些特殊情况，比如sentence中sent也是一个单词，还有其他重叠的情况。如果分离失败，如何回溯。

设字符串的长度为n, 

从第i(初值i=0)个字母开始，如果找到的不是单词，接着看下一个字母和目前的已经检测完的字母构不构成单词，如果构成单词，递归检测2~n-1，如果不构成，继续向前看；

如果第i个字母找到的是单词，将后面i+1~n-1的字母按同样的做法开始检测（递归）。

如果检测到最后一个字母时，发现目前已经检测完的字母未构成单词，那么回溯到上一次成功检测到单词的地方，将该单词后面加一个新的字母，然后接着按上面的做法。 如果回溯后直到最后也没有发现构成单词的，报告书输入字符串不构成句子。