华为OD机试中的中文分词模拟器题目，通常要求考生对给定的不包含空格的字符串进行精确分词。这个字符串仅包含英文小写字母及英文标点符号（如逗号、分号、句号等），同时会提供一个词库作为分词依据。以下是对这类题目的详细解析
一、题目描述
给定一个连续不包含空格的字符串Q，该字符串仅包含英文小写字母及英文标点符号(逗号、分号、句号)，同时给定词库，对该字符串进行精确分词。
说明:
1、精确分词:字符串分词后，不会出现重复。即"ilovechina"，不同词库可分割为"i,love,china"，“ilove,china”，不能分割出现重的"i,ilove,china"，i出现重复。
2、标点符号不成词，仅用于断句。
3、词库:根据外部知识库统计出来的常用词汇例:dictionary=[“i”,“ove”,“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”
用例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
四、分词原则
- 精确分词：字符串分词后，不会出现重叠的情况。
- 分词顺序：按照字符串从左到右的顺序进行分词。
- 最长匹配：在分词时，优先匹配词库中最长的符合条件的词汇。
- 标点符号：标点符号不成词，仅用于断句。
五、代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class PreciseSegmentation {
public static void main(String[] args) {
// 使用Scanner读取输入
Scanner scanner = new Scanner(System.in);
// 读取待分词的句子
String Q = scanner.nextLine();
// 读取词库字符串
String dictionaryStr = scanner.nextLine();
// 将词库转换为集合
Set<String> dictionary = new HashSet<>(Arrays.asList(dictionaryStr.split(",")));
// 分词结果
List<String> result = new ArrayList<>();
// 当前处理的起始位置
int start = 0;
// 开始分词处理
while (start < Q.length()) {
// 初始化结束位置
int end = start + 1;
// 用于存储最长匹配的词
String longestMatch = null;
// 寻找最长匹配的词
while (end <= Q.length()) {
// 获取子字符串
String sub = Q.substring(start, end);
// 检查子字符串是否在词库中
if (dictionary.contains(sub)) {
// 更新最长匹配的词
if (longestMatch == null || sub.length() > longestMatch.length()) {
longestMatch = sub;
}
}
// 移动结束位置
end++;
}
// 如果找到匹配的词，将其加入结果列表
if (longestMatch != null) {
result.add(longestMatch);
// 更新起始位置
start += longestMatch.length();
} else {
// 如果没有找到匹配的词，将单个字符加入结果列表
result.add(Q.substring(start, start + 1));
// 移动起始位置
start++;
}
}
// 输出结果
System.out.println(String.join(",", result));
}
}
六、解题思路
解题思路如下：
-
输入读取：
- 使用
Scanner类从标准输入读取两行数据。第一行是待分词的句子Q，第二行是词库字符串dictionaryStr。
- 使用
-
词库转换：
- 将词库字符串
dictionaryStr按逗号分隔，转换为String类型的列表。 - 使用
HashSet来存储词库中的词汇，以便进行快速的查找操作。这是因为HashSet的查找时间复杂度为O(1)，而列表的查找时间复杂度为O(n)。
- 将词库字符串
-
分词处理：
- 初始化一个空列表
result来存储分词结果。 - 初始化一个变量
start来记录当前处理的起始位置，初始值为0。 - 使用一个外层
while循环来遍历整个待分词的句子Q，直到start变量的值等于句子的长度。
- 初始化一个空列表
-
最长匹配查找：
- 在外层循环内部，初始化一个变量
end来表示当前查找的结束位置，初始值为start + 1。 - 初始化一个变量
longestMatch来存储当前找到的最长匹配的词汇，初始值为null。 - 使用一个内层
while循环来查找从start到end之间的所有可能的子字符串，并检查它们是否在词库中。 - 如果找到一个匹配的词汇，并且它的长度大于当前
longestMatch的长度（或者longestMatch为null），则更新longestMatch的值。 - 每次内层循环结束时，
end的值都会增加1，以继续查找下一个可能的子字符串。
- 在外层循环内部，初始化一个变量
-
结果处理：
- 当内层循环结束后，检查
longestMatch是否为null。 - 如果
longestMatch不为null，说明找到了一个匹配的词汇，将其添加到result列表中，并更新start的值为start + longestMatch.length()，以便继续处理下一个词汇。 - 如果
longestMatch为null，说明在当前位置没有找到匹配的词汇，此时将当前位置的单个字符作为一个词汇添加到result列表中，并将start的值增加1。
- 当内层循环结束后，检查
-
输出结果：
- 使用
String.join(",", result)将result列表中的词汇用逗号连接起来，形成一个字符串。 - 输出该字符串作为分词结果。
- 使用
这个解题思路遵循了最长匹配原则和分词顺序优先的原则，确保了分词结果的准确性和合理性。同时，通过使用HashSet来存储词库中的词汇，提高了查找效率。
七、运行示例解析
运行示例解析如下：
输入：
- 待分词的句子：
ilovechina - 词库字符串：
i,love,china,ch,na,ve,lo,this,is,the,word
步骤解析：
-
初始化：
Q = "ilovechina"- 词库字符串被分割并存储在
HashSet中，即dictionary = {i, love, china, ch, na, ve, lo, this, is, the, word} result = []（空列表，用于存储分词结果）start = 0（当前处理的起始位置）
-
分词处理：
- 外层
while循环开始，条件是start < Q.length()，即start < 9。
第一次外层循环：
end = start + 1 = 1- 内层
while循环开始，条件是end <= Q.length()，即1 <= 9。sub = Q.substring(0, 1) = "i"，dictionary.contains("i")返回true。- 更新
longestMatch = "i"。 end递增为2。sub = Q.substring(0, 2) = "il"，dictionary.contains("il")返回false。end递增为3。sub = Q.substring(0, 3) = "ilo"，dictionary.contains("ilo")返回false。end递增为4。sub = Q.substring(0, 4) = "ilov"，dictionary.contains("ilov")返回false。end递增为5。sub = Q.substring(0, 5) = "ilove"，dictionary.contains("ilove")返回false。end递增为6。sub = Q.substring(0, 6) = "ilovec"，dictionary.contains("ilovec")返回false。end递增为7。sub = Q.substring(0, 7) = "ilovech"，dictionary.contains("ilovech")返回false。end递增为8。sub = Q.substring(0, 8) = "ilovechi"，dictionary.contains("ilovechi")返回false。end递增为9。sub = Q.substring(0, 9) = "ilovechina"，dictionary.contains("ilovechina")返回false（虽然这不是词库中的词，但因为我们是从头开始找，所以会继续尝试更短的词）。- 内层循环结束，因为
end已经超过Q.length()。
longestMatch = "i"，将其加入result，即result = ["i"]。- 更新
start = 1。
后续的外层循环（类似地处理）：
start = 1时，找到longestMatch = "love"，加入result，即result = ["i", "love"]。start = 6时，找到longestMatch = "china"，加入result，即result = ["i", "love", "china"]。- 此时
start = 11，已经超过Q.length()，外层循环结束。
- 外层
-
输出结果：
- 使用
String.join(",", result)将result列表中的词汇用逗号连接起来，得到"i,love,china"。 - 输出该字符串。
- 使用
最终输出：
i,love,china
注意：在这个例子中，尽管词库中有一些无关的词（如ch, na, ve, lo等），但它们并没有影响分词的结果，因为分词算法总是尝试找到最长的匹配词。