最近刚刚打完ACM的校队选拔赛，最后幸运女神眷顾，压线进了校队[做梦笑醒的说]。在这段时间的集训中，新学习了很多很有意思的算法，今天就让我们一起来学习回文串题目的大杀器——回文树吧！ 思考一下 现在我们提出一个问题： 假如给你一个长度为 n 的字符串 S （n≤1e5），需要你求解本质不同的回文串的数量及各自的出现次数是多少（不包括空串）。[本质不同的字符串通俗来说就是长的不一样的字符串...
今天在某神犇老师的带领下学习了后缀自动机，刚开始学的时候还是一脸懵逼的，后面在周围大佬们孜孜不倦的帮助下终于学会了后缀数组。这篇BLOG，就让我们携手走进后缀数组吧。 什么是后缀数组 我们先来一个一个概念搞懂： 子串 若我们有一个长度为n的字符串S，设字符串内的点为[1,n]，那么我们从中任意截取一段[l,r], 若1≤l≤r≤n，那么称 截取出来的这段子字符串SS为原字符串的子串。即若...
AC自动机补档第二期……不懂KMP的同学可以好好学习一下这个神奇的单字符串匹配问题的算法吧！ 字符串匹配 什么叫字符串匹配呢？假设我们有一个主字符串和一个子串： 主串：abcbcglx 子串：bcgl 那么在主字符串中，有没有包含子串呢？当然，你一眼就看出，从主串的第4位到第7位恰好为子串 bcgl；这时我们的匹配算法就返回 4 也就是子串在主串中第一次出现的起始位置；若匹配失败，既...
在写完AC自动机后，就有小伙伴要求我具体讲解一下KMP和Trie树，那么这篇BLOG，就带你走进其实很简单的Trie树吧！ 什么是字典树 基本概念 字典树，又称为单词查找树或Tire树，是一种树形结构，它是一种哈希树的变种，用于存储字符串及其相关信息。 基本性质 1.根节点不包含字符，除根节点外的每一个子节点都包含一个字符 2.从根节点到某一节点。从根节点到该节点路径上经过的字符连接...
很久没更新BLOG了，甚至想接着发出咕咕咕的叫声。咳咳咳，这些都不重要!最近学习了一下AC自动机，发现其实远没有想象中的那么难，下面就让这篇BLOG教会你AC自动机吧！ AC自动机的来历 首先，我要说明！AC自动机并不是能自动AC的程序【刚开始天真的我也觉得学了AC自动机就无敌了QwQ】！！！ AC自动机之所以叫AC自动机，是因为这个算法原名叫Aho-Corasick automaton...