Skip to content

  • 体验新版
    • 正在加载...
  • 登录
  • KnowledgePlanet
  • docdoc
  • Issue
  • #23

doc
doc
  • 项目概览

KnowledgePlanet / doc

通知 1303
Star 822
Fork 117
  • 代码
    • 文件
    • 提交
    • 分支
    • Tags
    • 贡献者
    • 分支图
    • Diff
  • Issue 42
    • 列表
    • 看板
    • 标记
    • 里程碑
  • 合并请求 0
  • DevOps
    • 流水线
    • 流水线任务
    • 计划
  • Wiki 2
    • Wiki
  • 分析
    • 仓库
    • DevOps
  • 项目成员
  • Pages
doc
doc
  • 项目概览
    • 项目概览
    • 详情
    • 发布
  • 仓库
    • 仓库
    • 文件
    • 提交
    • 分支
    • 标签
    • 贡献者
    • 分支图
    • 比较
  • Issue 42
    • Issue 42
    • 列表
    • 看板
    • 标记
    • 里程碑
  • 合并请求 0
    • 合并请求 0
  • Pages
  • DevOps
    • DevOps
    • 流水线
    • 流水线任务
    • 计划
  • 分析
    • 分析
    • 仓库分析
    • DevOps
  • Wiki 2
    • Wiki
  • 成员
    • 成员
  • 收起侧边栏
  • 动态
  • 分支图
  • 创建新Issue
  • 流水线任务
  • 提交
  • Issue看板
已关闭
开放中
Opened 7月 26, 2023 by 小傅哥@Yao__Shun__Yu⛹Owner

使用 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();
    }
}
指派人
分配到
无
里程碑
无
分配里程碑
工时统计
无
截止日期
无
标识: KnowledgePlanet/doc#23
渝ICP备2023009037号

京公网安备11010502055752号

网络110报警服务 Powered by GitLab CE v13.7
开源知识
Git 入门 Pro Git 电子书 在线学 Git
Markdown 基础入门 IT 技术知识开源图谱
帮助
使用手册 反馈建议 博客
《GitCode 隐私声明》 《GitCode 服务条款》 关于GitCode
Powered by GitLab CE v13.7