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

//分词函数

parse(str) 

	for i = 1 to str.length

		substr = str.sub(1, i) //取子串

		if(dic(substr)) //dic是楼主给的函数

			set = parse(str.left) //解析剩下的部分

			if(!set.error) //解析结果没有错误, 返回结果

				return substr + set 

	

	return error //遍历所有, 依然得不到正确解析, 返回错误标识. 

//分词函数

parse(str) 

	for i = 1 to str.length

		substr = str.sub(1, i)

		if(dic(substr)) //dic是楼主给的函数

			set = parse(str.left)

			if(!set.error)

				return substr + set

	

	return error

// 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;

}