技术分享
未读
浅谈LCT(动态树)
一、算法简介 LCT(link−cut−tree) 是一种可以维护树上动态关系的数据结构。 主要思想是建立一座含有多棵 Splay 的森林以替代原来的树结构, 并通过 实链剖分 对树进行动态剖分实现的。 其复杂度是 O(qlogn) 级别的。
技术分享
未读
浅谈KMP算法 —— 高效字符串匹配
引言 字符串匹配是计算机科学里非常常见的问题,例如: 文本编辑器中的「查找」功能 DNA 序列比对 搜索引擎的关键词检索 设文本串长度为 n,模式串长度为 m,则朴素算法的时间复杂度是 O(nm),当文本和模式串都很长时效率很差。 KMP 算法 通过在匹配失败时利用已知的匹配信息来 减少回退,最终实
技术分享
未读
浅谈Manacher算法
一、算法简介 manacher算法是一款用于匹配回文串的线性算法。 其实现原理为利用回文串的对称性进行预处理回文串长度后暴力扩展。 二、原理实现 (以下解释均基于长度为奇数的回文串进行) 设右端点最靠右的回文串中回文中心为 mid,其右端点为 r,此时处理到的位置为 i
技术分享
未读
浅谈树链剖分(重链剖分)
一、算法简介 树链剖分是一种用于树上路径修改与求和的一种算法, 其核心原理是将链分为轻重,并通过轻重链的跳跃实现简便处理。 二、术语解释 1、重(轻)子节点: 子树大小最大的子节点被称为重子节点,除了重儿子以外的子节点均为轻子节点。
爱特工作室开展2024年第四季度优秀项目评审会
为了给计算机学院广大本科生提供“感受技术新知,激发无限潜能”的实践舞台,12月7日下午,爱特工作室联合CCF海大学生分会在西海岸校区58创新创业工坊开展优秀项目评审会。此次评审会吸引了众多爱特工作室成员的踊跃参与,他们带着各自精心打造的项目,满怀期待地希望在这个平台上展示团队的创新成果与技术实力。