算法

1. Dotcpp
2. 算法

回文树/回文自动机 (PAM) 实现及模板

咱们可以先从字面意思来理解什么是回文树，回文树(回文自动机)实际上是奇偶两棵树，每一个节点代表一个本质不同的回文子串（一棵树上的串长度全部是奇数，另一棵全部是偶数），原串中每一个本质不同的回文子串都在树上出现一次且仅一次。一个节点的fail指针指向它的最长回文后缀（不包括自身，

字符串相关 2022年04月15日 74 点赞 0 评论 56446 浏览

后缀自动机（单词的有向无环图）简介

在我们学习后缀自动机之前，一定要先了解什么是自动机？自动机（确定有限状态自动机）是由一个非空有限状态的集合Q、一个输入字母表Σ（非空有限字符的集合）、一个转移函数（单值映射）、一个开始状态、一个接受状态（终结状态）的集合所组成的5-元组。历史上，

字符串相关 2022年04月29日 223 点赞 0 评论 56478 浏览

树链剖分解决什么问题？

一、什么是树链剖分什么是树链剖分？它可以把树分成若干条链，从而维护树上的路径信息。本质思想是把树剖成可以用线性结构存储的结构，然后可以数据结构维护。分为三种：重链剖分、长链剖分、实链剖分。以下以重链剖分为主。二、树链剖分的思想及能解决的问题重链剖分可以将树上的任意一条路径划分成不超过O(logn)条连

图论 2022年01月25日 168 点赞 0 评论 59652 浏览

树的基础知识

一、什么是树树是一种类似链表的数据结构，不过链表的结点是以线性方式简单地指向其后继指点，而树的一个结点可以指向许多个结点。树是一种典型的非线性结构。树结构是表达具有层次特性的图结构的一种方法。二、相关术语●根结点：根结点就是一个没有双亲结点的结点。

图论 2022年01月30日 84 点赞 0 评论 60021 浏览

C++标准库中的字符串

一、C++字符串C++提供了以下两种类型的字符串表示形式：（1）C风格字符串（2）C++引入的string类类型二、C风格字符串C风格的字符串起源于C语言，并在C++中继续得到支持。字符串实际上是使用null字符\0终止的一维字符数组。因此，一个以null结尾的字符串，包含了组成字符串的字符。

字符串相关 2022年02月05日 170 点赞 0 评论 61313 浏览

计数DP实例讲解

本篇主要从计数DP上结合实例分析。一、计数类DP——整数划分整数划分大体上可以分为3类（1）考虑顺序的拆分方案（即1，1，2；和2，1，1是两种不同的方案），这种问题一般转化为完全背包即可解决。（2）不考虑顺序的拆分方案，可以划分出空集（也就是可以有对拆分完全没贡献的东西存在（0））（3）不考虑顺序的

动态规划 2022年04月04日 98 点赞 0 评论 61681 浏览

广义后缀自动机概述

广义后缀自动机的前置知识点是后缀自动机和字典树（Trie树）的相关内容，因为这两个知识点穿插在一起更容易理解和构建知识框架。当我们的是动机如何储存一个字符串的所有子串？该怎么办？怎么做？后缀自动机的作用就展现出来了。首先，后缀自动机起源于刘研绎在其2015国家队论文《后缀自动机在字典树上的拓展》上提出

字符串相关 2022年04月26日 108 点赞 0 评论 63789 浏览

悬线法实例讲解

先说说什么是悬线？就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。一、概述悬线法的适用范围是单调栈的子集。具体来说，悬线法可以应用于满足以下条件的题目：（1）需要在扫描序列时维护单调的信息；（2）可以使用单调栈解决；（3）不需要在单调栈上二分。

其他算法 2022年03月25日 83 点赞 0 评论 64703 浏览

树哈希常用的方式

树哈希，顾名思义，对树进行哈希，经常判断两个树是否同构。一下均为对有根树的算法，而无根树只需要找重心。我们有时需要判断一些树是否同构。这时，选择恰当的哈希方式来将树映射成一个便于储存的哈希值（一般是32位或64位整数）是一个优秀的方案。树哈希有很多种哈希方式，下面将选出几种较为常用的方式来加以介绍。

图论 2022年03月28日 143 点赞 0 评论 65100 浏览

最小表示法算法解析

提到最小表示法，要了解它的定义，最小表示法是用于解决字符串最小表示问题的方法。一算法简介：当一个字符串形成一个环的时候，要比较两个字符串是否相同就会变得很困难，因为你不知道对于第二个字符串来说，以哪个字符开始比较才会和第一个字符串相同。所以我们就会想到枚举起点比较是否相同，而这样的复杂度O(n^2)。

字符串相关 2022年03月10日 142 点赞 0 评论 65328 浏览