2025华为od机试E卷【中文分词模拟器】C语言实现

给定一个连续不包含空格的字符串，该字符串仅包含英文小写字母及英文标点符号(逗号、分号、句号)，同时给定词库，对该字符串进行精确分词。

MISAYAONE

1838人浏览 · 2025-03-06 15:00:00

MISAYAONE · 2025-03-06 15:00:00 发布

题目

思路

Code

题目

给定一个连续不包含空格的字符串，该字符串仅包含英文小写字母及英文标点符号(逗号、分号、句号)，同时给定词库，对该字符串进行精确分词。
说明:
1.精确分词: 字符串分词后，不会出现重叠
即"ilovechina",不同词库可分割为",love,china”，“ilove,china”不能分割出现重叠的"ilove,china"i 出现重叠。
2.标点符号不成词，仅用于断句
3.词库: 根据外部知识库统计出来的常用词汇例:
dictionary =["i",“love”,“china”,“lovechina”,“ilove”]
4.分词原则: 采用分词顺序优先且最长匹配原则
“llovechina”假设分词结果[i,ilove,lo,love,ch,china,lovechina],则输出[ilove,china]
错误输出: [i,lovechina],原因:“ilove”>优先于"lovechina"成词

错误输出: [i,love,china],原因:“love”>"遵循最长匹配原则

输入描述
第一行输入待分词语句 S
第二行输入中文词库
字符串 S 长度限制: 0 < S.length < 256
词库长度限制: 1 < length < 100000
输出描述
按顺序输出分词结果

示例1：

输入：

ilovechina
i,love,china,ch,na,ve,lo,this,is,the,word

输出：

i,love,china

示例2：

输入：

iat
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful

输出：

i,a,t

示例3：

输入：

ilovechina,thewordisbeautiful
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful

输出：

i,love,china,the,word,is,beauti,ful

思路

算法思路

标点符号分割句子
根据标点符号（逗号、分号、句号）将输入字符串拆分为多个子句。每个子句独立分词，最后合并结果。

构造词典（字典树）
使用 Trie（字典树）存储词库，支持高效的最长匹配查询。

分词规则

最长匹配优先：从当前位置开始，尽可能匹配最长的词。

按顺序匹配：若出现多个词的分割情况，优先选取靠前的分词方案。

逐句分词
对于每个子句，从左到右扫描，通过 Trie 查找最长匹配的词，若无法匹配，取当前字符为单词。

结果合并
将所有子句的分词结果合并为最终答案。

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_LEN 256
#define MAX_WORDS 100000

// 结构体定义哈希表节点
typedef struct WordNode {
    char word[50];
    struct WordNode *next;
} WordNode;

#define HASH_SIZE 10007  // 选择一个较大的素数作为哈希表大小
WordNode *hashTable[HASH_SIZE];

// 哈希函数
unsigned int hashFunction(const char *str) {
    unsigned int hash = 0;
    while (*str) {
        hash = (hash * 31 + (*str)) % HASH_SIZE;
        str++;
    }
    return hash;
}

// 向哈希表插入单词
void insertWord(const char *word) {
    unsigned int index = hashFunction(word);
    WordNode *newNode = (WordNode *)malloc(sizeof(WordNode));
    strcpy(newNode->word, word);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 在哈希表中查找单词
int findWord(const char *word) {
    unsigned int index = hashFunction(word);
    WordNode *node = hashTable[index];
    while (node) {
        if (strcmp(node->word, word) == 0) {
            return 1;
        }
        node = node->next;
    }
    return 0;
}

// 释放哈希表
void freeHashTable() {
    for (int i = 0; i < HASH_SIZE; i++) {
        WordNode *node = hashTable[i];
        while (node) {
            WordNode *temp = node;
            node = node->next;
            free(temp);
        }
        hashTable[i] = NULL;
    }
}

// 分割输入字符串，处理逗号、分号、句号作为分隔符
void splitSentence(char *input, char words[][50], int *count) {
    char *token = strtok(input, ",;.\n");
    while (token != NULL) {
        strcpy(words[*count], token);
        (*count)++;
        token = strtok(NULL, ",;.\n");
    }
}

int main() {
    char inputStr[MAX_LEN];
    char dictStr[MAX_WORDS];
    char words[MAX_WORDS][50];
    int wordCount = 0;
    
    // 读取输入字符串
    fgets(inputStr, MAX_LEN, stdin);
    inputStr[strcspn(inputStr, "\n")] = 0; // 去掉换行符
    
    // 读取词库
    fgets(dictStr, MAX_WORDS, stdin);
    dictStr[strcspn(dictStr, "\n")] = 0; // 去掉换行符
    
    // 解析词库并存入哈希表
    splitSentence(dictStr, words, &wordCount);
    for (int i = 0; i < wordCount; i++) {
        insertWord(words[i]);
    }
    
    int len = strlen(inputStr);
    int dp[MAX_LEN + 1] = {0};
    dp[len] = 1;
    
    // 进行动态规划
    for (int i = len - 1; i >= 0; i--) {
        for (int j = 1; j <= len - i; j++) {
            char temp[50];
            strncpy(temp, inputStr + i, j);
            temp[j] = '\0';
            if (findWord(temp) && dp[i + j]) {
                dp[i] = 1;
                break;
            }
        }
    }
    
    // 输出分词结果
    if (dp[0]) {
        int i = 0;
        while (i < len) {
            int maxLen = -1;
            for (int j = 1; j <= len - i; j++) {
                char temp[50];
                strncpy(temp, inputStr + i, j);
                temp[j] = '\0';
                if (findWord(temp) && dp[i + j] && j > maxLen) {
                    maxLen = j;
                }
            }
            if (maxLen > 0) {
                if (i > 0) printf(",");
                printf("%.*s", maxLen, inputStr + i);
                i += maxLen;
            }
        }
    } else {
        for (int i = 0; i < len; i++) {
            if (i > 0) printf(",");
            printf("%c", inputStr[i]);
        }
    }
    
    printf("\n");
    freeHashTable(); // 释放内存
    return 0;
}

要求

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

语言限定：
C（clang11）, C++（clang++11）, Pascal（fpc 3.0.2）, Java（javac 1.8）, Python2（2.7.3）,
PHP(7.4.7), C#(mcs5.4), ObjC(gcc 5.4), Pythen3(3.9), JavaScript Node(12.18.2), JavaScript V8(6.0.0),
Sqlite(3.7.9), R(4.0.3), Go(1.14.4), Ruby(2.7.1), Swift(5.3), matlab(Octave 5.2), Pypy2(pypy2.7.13),
Pypy3(pypy3.6.1), Rust(1.44), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2), Mysql(8.0)