使用 Trie 树(字典树)来实现词表存储和匹配。Trie 树是一种树形结构,用于存储字符串集合,可以快速地查找、插入和删除字符串。
import java.util.*;
public class BrandMatcher {
// Trie 树节点
static class TrieNode {
boolean isEnd; // 是否是某个品牌关键词的结尾节点
Map<Character, TrieNode> children; // 子节点
public TrieNode() {
isEnd = false;
children = new HashMap<>();
}
}
// Trie 树
static class Trie {
TrieNode root; // 根节点
public Trie() {
root = new TrieNode();
}
// 插入一个品牌关键词
public void insert(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (!cur.children.containsKey(c)) {
cur.children.put(c, new TrieNode());
}
cur = cur.children.get(c);
}
cur.isEnd = true;
}
// 查找一个字符串是否匹配某个品牌关键词
public boolean search(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (cur.children.containsKey(c)) {
cur = cur.children.get(c);
} else {
cur = root;
}
}
return cur.isEnd;
}
}
// 合并多个 Trie 树
public static Trie mergeTries(List<Trie> tries) {
Trie mergedTrie = new Trie();
for (Trie trie : tries) {
mergeTrieNode(mergedTrie.root, trie.root);
}
return mergedTrie;
}
// 合并两个 Trie 树节点
private static void mergeTrieNode(TrieNode node1, TrieNode node2) {
if (node2.isEnd) {
node1.isEnd = true;
}
for (char c : node2.children.keySet()) {
TrieNode child2 = node2.children.get(c);
if (!node1.children.containsKey(c)) {
node1.children.put(c, new TrieNode());
}
TrieNode child1 = node1.children.get(c);
mergeTrieNode(child1, child2);
}
}
public static void main(String[] args) {
// 读入品牌词表,构建 Trie 树
Trie trie1 = new Trie();
Trie trie2 = new Trie();
// 读入词表文件,每行为一个品牌关键词
// 假设第一种规则的品牌关键词以【】开头,第二种规则的品牌关键词以|分隔
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (line.startsWith("【")) {
String word = line.substring(1, line.indexOf("】"));
trie1.insert(word);
} else if (line.contains("|")) {
String[] words = line.split("\\|");
for (String word : words) {
trie2.insert(word);
}
}
}
scanner.close();
// 合并多个 Trie 树
List<Trie> tries = new ArrayList<>();
tries.add(trie1);
tries.add(trie2);
Trie mergedTrie = mergeTries(tries);
// 读入待匹配数据,逐行匹配
scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (mergedTrie.search(line)) {
System.out.println(line);
}
}
scanner.close();
}
}