号称微软面试题之 如何分隔没有空格标点的英文句子

原帖地址：

采用 回溯加递归的方法，进行了实现。

// test.cpp : Defines the entry point for the console application.
//

/*http://topic.csdn.net/u/20110526/16/e33f016b-f188-42b7-afce-b4eca9e3546d.html
给你一个没有间隔的字符串“thisisasentence”，如何将他分割成如下的句子：“this is a sentence”。
提供一个函数用来检验一个字符串是不是单词：bool dic(char* w)；
完成下列的函数。要求效率尽可能快。
bool Detect(char* str)
{

}
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
#include "string.h"


#define MAX_WORD_COUNT 5
#define MAX_DIVIDE 10
#define MAX_WORD_LENGTH 30
int num[MAX_WORD_COUNT]={0};
int divide[MAX_DIVIDE] = {0};
#define FALSE 0
#define TRUE 1
int ii=0, jj=0;
/* If w is a word, store the number of characters in num[] Array.
 * Number of the cases where w can stand for a word is stored in a int, which is marked by the pointer pCnt*/
bool dic(char* w, int* pCnt)
{
    int i=0, j=0;
    bool flag = FALSE;
    for (i=0; i<MAX_WORD_COUNT; ++i)
    {
        num[i]=0;
    }
    int test=0;
    if (!(strncmp(w, "this", strlen("this"))))
    {
        num[j++] = 4;
        ++(*pCnt);
        flag = TRUE;
    }
    if (!strncmp("is", w, strlen("is")))
    {
        num[j++] = 2;
        ++(*pCnt);
        flag = TRUE;
    }
    if (!strncmp("a", w, strlen("a")))
    {
        num[j++] = 1;
        ++(*pCnt);
        flag = TRUE;
    }
    if (!strncmp("sentence", w, strlen("sentence")))
    {
        num[j++] = 8;
        ++(*pCnt);
        flag = TRUE;
    }
    if (!strncmp("sent", w, strlen("sent")))/*test case*/
    {
        num[j++] = 4;
        ++(*pCnt);
        flag = TRUE;
    }
    return flag;
}

bool Detect(char* str)
{

    int cnt_tmp = 0;

    if (*str == '\0')
    {
        return TRUE;
    }
    if (dic(str, &cnt_tmp))
    {
        divide[jj++] = num[ii];
        for (ii=0; ii < cnt_tmp; ++ii)
        {
            if (Detect(&str[num[ii]]))
            {
                return TRUE;
            }
            else
            {
                divide[--jj] = 0;
            }
        }
    }
    return FALSE;
}

int main()
{
    /* print*/
    int* pDiv=divide;
    char* pCh="thisisasentence";
    char tmp[MAX_WORD_LENGTH];

    memset(divide, 0, MAX_DIVIDE*sizeof(int));

    if (Detect(pCh))
    {
        while (*pDiv)
        {
            memset(tmp, 0, MAX_WORD_LENGTH);
            strncpy(tmp, pCh, *pDiv);
            printf("%s ", tmp);
            pCh = pCh+(*pDiv);
            ++pDiv;
        }
        printf("\n");
    }
    return 0;
}