#include <stdio.h>
#include <string>
#include <set>
using namespace std;
set<string> g_setWordDictionary;

int construct()
{
g_setWordDictionary.insert("中國");
g_setWordDictionary.insert("中國人");
g_setWordDictionary.insert("紐約");
g_setWordDictionary.insert("北京");
}

bool match(string &word)
{
set<string>::iterator itor = g_setWordDictionary.find(word);
if (itor == g_setWordDictionary.end())
{
return false;
}

return true;
}

void forward_maximum_matching(string content, set<string> &keywords)    
{
#define MAX_LEN 12      //詞庫中最長詞語(utf-8一個漢字3個字節)
#define MIN_LEN 3       //單字(原理同上)
int len = content.length();
int right_len = len;
int start_pos = 0;
bool ret = false;
string kw_value = "";
int kw_len = 0;
int kw_pos = 0;
//單字或空串
while (right_len > MIN_LEN)
{
//語句大于詞庫中最長詞語
if (right_len >= MAX_LEN)
{
kw_value = content.substr(start_pos, MAX_LEN);
}
//語句小于詞庫中最長詞語
else
{
kw_value = content.substr(start_pos, right_len);
}

//詞庫匹配
ret = match(kw_value);
kw_len = kw_value.length();
kw_pos = 0;
while (!ret && kw_len > 2*MIN_LEN)
{
//去掉候選詞右邊一個漢字
kw_len -= MIN_LEN;
kw_value = kw_value.substr(kw_pos, kw_len);
//繼續匹配
ret = match(kw_value);
}

//匹配到詞
if (ret)
{
keywords.insert(kw_value);
//從語句中去掉匹配到的詞
start_pos += kw_len;
right_len = len - start_pos;
}
//未匹配到詞，下移一個字
else
{
start_pos += MIN_LEN;
right_len = len - start_pos;
}
}//while (right_len > MIN_LEN)      
}

int main()
{
//構造詞庫
construct();

//切分詞庫
string content = "我是中國人，我是來自中國北京的中國人，在紐約工作";
set<string> keywords;
forward_maximum_matching(content, keywords);
set<string>::iterator itor;

//輸出分詞
for (itor=keywords.begin(); itor!=keywords.end(); ++itor)
{
printf("result: %s\n", (*itor).c_str());
}

return 0;
}