(C卷,200分)- 中文分词模拟器（Java & JS & Python & C）

题目描述

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

说明：

1. 精确分词：字符串分词后，不会出现重叠。即"ilovechina"，不同词库可分割为"i,love,china"，"ilove,china"，不能分割出现重叠的"i,ilove,china"，i 出现重叠
2. 标点符号不成词，仅用于断句
3. 词库：根据外部知识库统计出来的常用词汇例：dictionary = ["i", "love", "china", "lovechina", "ilove"]
4. 分词原则：采用分词顺序优先且最长匹配原则

   "ilovechina"，假设分词结果 [i,ilove,lo,love,ch,china,lovechina]，则输出 [ilove,china]

   错误输出：[i,lovechina]，原因："ilove" > 优先于 "lovechina" 成词

   错误输出：[i,love,china]，原因："ilove" > "i"遵循最长匹配原则

输入描述

第一行输入待分词语句 "ilovechina"

• 字符串长度限制：0 < length < 256

第二行输入中文词库 "i,love,china,ch,na,ve,lo,this,is,this,word"

• 词库长度限制：1 < length < 100000

输出描述

按顺序输出分词结果 "i,love,china"

用例

题目解析

本题感觉题意不是很清晰。

我对题目的理解是：

句子：ilovechina

词库：[i,love,china,ch,na,ve,lo,this,is,the,word]

现在要用词库里面的词汇组成句子。并且选择词汇时，优先选择词库中靠前的，且长度最长的。

比如组成句子“ilovechina”的第一个词汇，必然是 "i" 开头的，因此我们去词库中找 "i" 开头的词汇，按词库顺序依次是：

• i
• is

其中 is 虽然是 i 开头，但是不符合句子后续部分要求，因此选择词库中词汇 “i”。

此时句子还剩下 "lovechina" 没有分词，则继续在词库中查找 "l" 开头的词汇，按词库顺序依次是：

• love
• lo

其中 "love" 是顺序靠前，且长度较长的，因此选择词库中词汇 "love"。

此时句子还剩下 "china" 没有分词，则继续在词库中查找 "c" 开头的词汇，按词库顺序依次是：

• china
• ch

其中 "china" 是顺序靠前，且长度较长的，因此选择词库中词汇 "china"。

此时句子"ilovechina" 完成分词，分词结果为：["i", "love", "china"]。

本题，我的疑惑主要在于用例2：

句子："iat"

词库：[i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful]

按照之前的逻辑，首先找到组成句子的第一个词汇，该词汇必然以"i"开头，则匹配到词库中的词汇"i"。

接下来句子还剩"at"，再去词库中查找"a"开头的词汇，发现没有。那么此时我的疑问来了：

• 是只针对句子剩余部分"at"，进行输出单个字母的操作
• 还是针对整个句子"iat"，进行输出单个字母的操作

对于这个用例，两种策略的输出结果都是一样，因为这个用例给的太有歧义了。

比如我给个例子：

句子：iloveat

词库：[i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful]

此时输出：i,love,a,t 

还是输出：i,l,o,v,e,a,t

不在词库中且不成词则输出单个字母

上面我给的例子，i 在词库中，love在词库中，at不在词库中，因此只针对at执行输出单个字母操作。

一次你，我理解是输出：i,love,a,t 

另外，不成词是什么意思呢？

题目中关于"不成词"，只有一个相关描述：标点符号不成词，仅用于断句

那么是不是就是说，标点符号不成词，英文小写字母成词呢？我理解应该是的。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 输入输出处理
void (async function () {
  const sentences = (await readline()).split(/[,.;]/);
  const words = (await readline()).split(/[,.;]/);

  console.log(getResult(sentences, words));
})();

function getResult(sentences, words) {
  // wordSet 记录词库词汇
  const wordSet = new Set(words);

  // ans记录最终分词结果
  const ans = [];

  while (sentences.length > 0) {
    const sentence = sentences.shift();

    let r = sentence.length;
    for (; r > 0; r--) {
      // 截取句子 [0,r) 范围子串词汇, 这样的就能实现优先最长匹配，并且由于是必须从0索引开始截取，因此满足了分词顺序优先
      const fragment = sentence.slice(0, r);

      // 若词库中是否存在该子串词汇
      if (wordSet.has(fragment)) {
        // 则将对应子串词汇纳入结果
        ans.push(fragment);
        wordSet.delete(fragment); // 我理解词库中每个词汇只能使用一次，因此这里将词库中使用过的词汇移除

        // 若子串词汇只是句子部分，则句子剩余部分还要继续去词库中查找
        if (r < sentence.length) {
          sentences.unshift(sentence.slice(r));
        }

        break;
      }
    }

    // 没有在词库中找到对应子串词汇，则输出单个字母
    if (r == 0) {
      // 注意，这里只放一个字母到结果中，句子剩余部分继续去词库中查找
      ans.push(sentence[0]);

      if (sentence.length > 1) {
        sentences.unshift(sentence.slice(1));
      }
    }
  }

  return ans.join(",");
}

Java算法源码

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] sentences = sc.nextLine().split("[,.;]");
    String[] words = sc.nextLine().split("[,.;]");

    System.out.println(getResult(sentences, words));
  }

  public static String getResult(String[] sentences, String[] words) {
    // wordSet 记录词库词汇
    HashSet<String> wordSet = new HashSet<>(Arrays.asList(words));

    // queue记录待分词语句
    LinkedList<String> queue = new LinkedList<>(Arrays.asList(sentences));

    // ans记录最终分词结果
    LinkedList<String> ans = new LinkedList<>();

    while (queue.size() > 0) {
      // 待分词的句子
      String sentence = queue.removeFirst();

      int r = sentence.length();
      for (; r > 0; r--) {
        // 截取句子 [0,r) 范围子串词汇, 这样的就能实现优先最长匹配，并且由于是必须从0索引开始截取，因此满足了分词顺序优先
        String fragment = sentence.substring(0, r);

        // 若词库中是否存在该子串词汇
        if (wordSet.contains(fragment)) {
          // 则将对应子串词汇纳入结果
          ans.addLast(fragment);
          wordSet.remove(fragment); // 我理解词库中每个词汇只能使用一次，因此这里将词库中使用过的词汇移除

          // 若子串词汇只是句子部分，则句子剩余部分还要继续去词库中查找
          if (r < sentence.length()) {
            queue.addFirst(sentence.substring(r));
          }

          break;
        }
      }

      // 没有在词库中找到对应子串词汇，则输出单个字母
      if (r == 0) {
        // 注意，这里只放一个字母到结果中，句子剩余部分继续去词库中查找
        ans.add(sentence.charAt(0) + "");

        if (sentence.length() > 1) {
          queue.addFirst(sentence.substring(1));
        }
      }
    }

    StringJoiner sj = new StringJoiner(",");
    ans.forEach(sj::add);

    return sj.toString();
  }
}

Python算法源码

import re

# 输入获取
sentences = re.split(r"[,.;]", input())
words = re.split(r"[,.;]", input())


def getResult():
    # wordSet 记录词库词汇
    wordSet = set(words)
    # ans记录最终分词结果
    ans = []

    while len(sentences) > 0:
        # 待分词的句子
        sentence = sentences.pop(0)

        r = len(sentence)
        while r > 0:
            # 截取句子 [0,r) 范围子串词汇, 这样的就能实现优先最长匹配，并且由于是必须从0索引开始截取，因此满足了分词顺序优先
            fragment = sentence[0:r]

            # 若词库中是否存在该子串词汇
            if fragment in wordSet:
                # 则将对应子串词汇纳入结果
                ans.append(fragment)
                wordSet.remove(fragment)  # 我理解词库中每个词汇只能使用一次，因此这里将词库中使用过的词汇移除

                # 若子串词汇只是句子部分，则句子剩余部分还要继续去词库中查找
                if r < len(sentence):
                    sentences.insert(0, sentence[r:])

                break

            r -= 1

        # 没有在词库中找到对应子串词汇，则输出单个字母
        if r == 0:
            # 注意，这里只放一个字母到结果中，句子剩余部分继续去词库中查找
            ans.append(sentence[0])

            if len(sentence) > 1:
                sentences.insert(0, sentence[1:])

    return ",".join(ans)


print(getResult())

C算法源码

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

#define MAX_LENGTH 256
#define MAX_WORDS_LENGTH 100000
#define delimiter ",.;"
#define TRUE 1
#define FALSE 0

/** 实现双向链表 **/
typedef struct ListNode {
    char *val;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

ListNode *new_ListNode(char *val) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->val = (char *) calloc(MAX_LENGTH, sizeof(char));
    strcpy(node->val, val);
    node->prev = NULL;
    node->next = NULL;
    return node;
}

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addFirst_LinkedList(LinkedList *link, char *val) {
    ListNode *node = new_ListNode(val);

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        node->next = link->head;
        link->head->prev = node;
        link->head = node;
    }

    link->size++;
}

void addLast_LinkedList(LinkedList *link, char *val) {
    ListNode *node = new_ListNode(val);

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }

    link->size++;
}

char *removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
        link->head->prev = NULL;
    }

    link->size--;

    char *res = (char *) calloc(MAX_LENGTH, sizeof(char));
    strcpy(res, removed->val);

    free(removed);

    return res;
}

char *removeLast_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->tail;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->tail = link->tail->prev;
        link->tail->next = NULL;
    }

    link->size--;

    char *res = (char *) calloc(MAX_LENGTH, sizeof(char));
    strcpy(res, removed->val);

    free(removed);

    return res;
}

/** 实现字符串截取 **/
char *substr(char *s, int l, int r) {
    int len = r - l;
    char *res = (char *) calloc(len + 1, sizeof(char));
    strncpy(res, s + l, len);
    return res;
}

int main() {
    char s1[MAX_LENGTH];
    gets(s1);

    // sentences记录待分词语句
    LinkedList *sentences = new_LinkedList();
    char *token1 = strtok(s1, delimiter);
    while (token1 != NULL) {
        addLast_LinkedList(sentences, token1);
        token1 = strtok(NULL, delimiter);
    }

    char s2[MAX_WORDS_LENGTH];
    gets(s2);

    // words 记录词库词汇
    LinkedList *words = new_LinkedList();
    char *token2 = strtok(s2, delimiter);
    while (token2 != NULL) {
        addLast_LinkedList(words, token2);
        token2 = strtok(NULL, delimiter);
    }

    // ans记录最终分词结果
    LinkedList *ans = new_LinkedList();

    while (sentences->size > 0) {
        char *sentence = removeFirst_LinkedList(sentences);

        int len = (int) strlen(sentence);
        int r = len;

        for (; r > 0; r--) {
            // 截取句子 [0,r) 范围子串词汇, 这样的就能实现优先最长匹配，并且由于是必须从0索引开始截取，因此满足了分词顺序优先
            char *fragment = substr(sentence, 0, r);

            int find = FALSE;

            ListNode *cur = words->head;
            while (cur != NULL) {
                // 若词库中是否存在该子串词汇
                if (strcmp(cur->val, fragment) == 0) {
                    // 则将对应子串词汇纳入结果
                    addLast_LinkedList(ans, fragment);
                    strcpy(cur->val, ""); // 我理解词库中每个词汇只能使用一次，因此这里将词库中使用过的词汇移除

                    // 若子串词汇只是句子部分，则句子剩余部分还要继续去词库中查找
                    if (r < len) {
                        addFirst_LinkedList(sentences, substr(sentence, r, len));
                    }

                    find = TRUE;

                    break;
                }
                cur = cur->next;
            }

            if (find) {
                break;
            }
        }

        // 没有在词库中找到对应子串词汇，则输出单个字母
        if (r == 0) {
            // 注意，这里只放一个字母到结果中，句子剩余部分继续去词库中查找
            char tmp[] = {sentence[0], ''};
            addLast_LinkedList(ans, tmp);

            if (len > 1) {
                addFirst_LinkedList(sentences, substr(sentence, 1, len));
            }
        }
    }

    ListNode *cur = ans->head;

    while (cur != NULL) {
        printf("%s", cur->val);
        cur = cur->next;
        if (cur != NULL) {
            printf(",");
        }
    }

    return 0;
}