技术分享
未读
从零开始：手把手教你实现一个 C++ 的 std::variant (基础数据结构复现实战)
前言 你好，C++ 探索者！你是否曾对 std::variant 的内部机制感到好奇？ 这个 C++17 引入的“类型安全的联合体”，究竟是如何在编译期施展魔法，从而在运行时优雅地存储多种不同类型的值的？ 这篇博客就是为你准备的钥匙。我们将一起打开 variant 的引擎盖，亲手用 C++ 模板元编
技术分享
未读
浅谈LCT（动态树）
一、算法简介 LCT(link−cut−tree) 是一种可以维护树上动态关系的数据结构。 主要思想是建立一座含有多棵 Splay 的森林以替代原来的树结构， 并通过 实链剖分 对树进行动态剖分实现的。 其复杂度是 O(qlogn) 级别的。
技术分享
未读
浅谈KMP算法 —— 高效字符串匹配
引言 字符串匹配是计算机科学里非常常见的问题，例如： 文本编辑器中的「查找」功能 DNA 序列比对 搜索引擎的关键词检索 设文本串长度为 n，模式串长度为 m，则朴素算法的时间复杂度是 O(nm)，当文本和模式串都很长时效率很差。 KMP 算法 通过在匹配失败时利用已知的匹配信息来 减少回退，最终实
技术分享
未读
浅谈Manacher算法
一、算法简介 manacher算法是一款用于匹配回文串的线性算法。 其实现原理为利用回文串的对称性进行预处理回文串长度后暴力扩展。 二、原理实现 （以下解释均基于长度为奇数的回文串进行） 设右端点最靠右的回文串中回文中心为 mid，其右端点为 r，此时处理到的位置为 i
技术分享
未读
浅谈树链剖分（重链剖分）
一、算法简介 树链剖分是一种用于树上路径修改与求和的一种算法， 其核心原理是将链分为轻重，并通过轻重链的跳跃实现简便处理。 二、术语解释 1、重（轻）子节点： 子树大小最大的子节点被称为重子节点，除了重儿子以外的子节点均为轻子节点。