喂你脚下有坑 3年前 Manacher 算法 回文串 字符串 Manacher 算法 问题设定 回文字符串，就是一个字符串，你从前向后读它与从后向前读它是一样的。比如：baccab 就是一个回文串，而且是一个长度为偶数的回文串（偶回文串）；bacdcab 是一个长度为奇数的回文串（奇回文串），babcb 就不是一个回文串。 这里可以发现，奇回文串的中心是一个字母，偶回文串的中心在最中 […] 算法竞赛 1.88k 0 7
喂你脚下有坑 4年前 KMP 字符串 模式匹配 KMP 算法 KMP 是一种模式匹配算法，要解决的问题可以形式化为：给定模式串 T 与目标串 S，我们要在目标串 S 中寻找 T 的所有出现。 为何暴力算法可以加速 提前剧透一下，KMP 算法使用模式串自己与自己进行匹配，得到了每一个前缀 $T[1\cdots x]$ 的最长相等前后缀（除自身外）的长度，从而在同 […] 算法竞赛 1.27k 0 8
喂你脚下有坑 4年前 KMP 字符串 模式匹配 算法模版 KMP 算法模版 给你一个模式串 T 与一个目标串 S，我们要快速找到 T 在 S 中的所有出现，复杂度为 $O(|S| + |T|)$。 需要额外说明的是这里的代码对于 Next 数组多算了一位，相当于给原本的模式串 T 后增加了一个无法匹配的字符。在匹配的过程中一旦要比较模式串无法匹配的字符，那么就说明匹配成功了 […] 算法竞赛 1.37k 0 2
喂你脚下有坑 4年前 后缀数组 字符串 模板 后缀数组模版 简介 给定一个 $0-Based$ 字符串 Str，将它的所有后缀进行排序。 数组 $sa[i]$ 中保存排名第 $i$ 的后缀的在字符串的那个位置，数组 $rank[i]$ 表示从位置 i 开始的子串的排名。 数组 $height[i]$ 表示排名第 $i$ 的字符串和排名第 $i+1$ 的字符串 […] 算法竞赛 884 0 0
喂你脚下有坑 4年前 AC自动机 字符串 AC 自动机模版 简述 处理多模式串匹配问题，初始化后(init)，先插入所有模式串(insert)，然后构建AC自动机(build)，最后进行匹配(next)。 假设模式串集合为 ${S}$，目标串为 $T$，那么算法复杂度为 $O(Simga_i |S_i| + |T|)$。 原理 等待填坑& […] 算法竞赛 863 0 1
喂你脚下有坑 7年前 字符串 暴力 模拟 Codeforces #360 A&B 传送门：http://codeforces.com/contest/688/problem/A 题目大意 Arya 有 n 个敌人和 d 天。 d 行 n 列，表示敌人的出勤情况 如果敌人不全勤，那么 Arya 可以击败所有敌人。 求 Arya 的最大连续击败敌人天数。 题解 模拟一下每一天统计即可 […] 算法竞赛 608 0 0
喂你脚下有坑 8年前 OI 字符串 脑洞 BZOJ 3916: [Baltic2014]friends Description 有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S. Input 第一行一个数N,表示U的长度. 第二行一个字符串U,保证U由大写字母组成 Output 输出一行,若S不存在 […] 算法竞赛 640 0 0
喂你脚下有坑 9年前 OI 字符串 模拟 BZOJ 2295: 【POJ Challenge】我爱你啊 Description ftiasch是个十分受女生欢迎的同学，所以她总是收到许多情书。虽然她十分有魅力，然而她却是个低调的人。因此她从来不会告诉别人她到底收到了多少情书。 ftiasch的好朋友1tthinking想知道她到底收到了多少情书。1tthinking知道，ftiasch每次收到一封情书 […] 算法竞赛 807 7 0
