Shaun's blog
welcome
  文章分类
2021ACM寒假集训 12 2022杭电多校 4 2022牛客多校 3 面试 2 算法学习 2 狂刷字符串 8 cf总结 4 一些感悟 1 博客搭建 1 python爬虫学习 2 cs162 1 计网学习 1 redis 1 sql 1 个人板子总结 1
cf-edu134-E，KMP的代替物？（速度超快） cf-edu134-E，KMP的代替物？（速度超快）
Prefix Function Queries题目传送门 题意有一个长度为 $n(1 \leq n \leq 10^6)$ 的字符串 $s$ ，有 $q(1 \leq q \leq 10^5)$ 次询问。 每次询问给出一个非空字符串 $t(
2022-08-29 狂刷字符串
acm 字符串
洛谷P6292，个人认为的字符串神仙题目 洛谷P6292，个人认为的字符串神仙题目
区间本质不同子串个数题目传送门 前言借鉴了题解中的这篇。 起因 前面多校训练的时候，出了一道和这道题十分类似但是又差别很大的题目。于是想着先把这道题给学会了，然后再尝试写多校训练中出现的那道题目。 本题知识点一览 $SAM$ + $LCT$
2022-08-26 狂刷字符串
acm LCT 字符串 后缀自动机 线段树 扫描线 离线
hdu7192,巧用sam hdu7192,巧用sam
AC/DC题目传送门 前言这是2022hdu多校第5场的1008，当时因为通过率过低，题目都没看，结束后看了之后发现是道 $SAM$ 好题，在这里补一下。 题目大意给出一个初始字符串 $s$ ，有三种操作 $1\ c$ : 在 $s$ 的
2022-08-05 狂刷字符串
acm 字符串 后缀自动机
2021江苏省赛H题 2021江苏省赛H题
Reverse the String题目传送门 题意给出一个字符串，有一种操作，将其中一个子串反转，我们可以进行最多一次这样的操作，需要使得这个字符串字典序最小。 $T$ 组数据， $1 \leq |s| \leq 10^5$ ， $\su
2022-08-01 狂刷字符串
acm 字符串 字符串哈希 二分
codeforces-edu131-E-Text Editor codeforces-edu131-E-Text Editor
Text Editor题目传送门 题目大意给出两个字符串 $a$ 和 $s$ ，长度分别为 $n$ 和 $m$ ，且 $1≤m≤n≤5000$ ，问经过最少多少次操作能从 $a$ 串变成 $s$ 串，如果不能输出 $-1$ 。初始时光标位于
2022-07-09 狂刷字符串
acm 字符串 扩展KMP 最长公共子串
洛谷P5357，关于AC自动机的优化方案 洛谷P5357，关于AC自动机的优化方案
【模板】AC 自动机（二次加强版）题目传送门 题目大意给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$ ，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。 当时写题过程 当时看到题目后，看着和前面一个
2022-06-30 狂刷字符串
acm 字符串 AC自动机
洛谷P3294，一道思路奇妙的Trie树题目 洛谷P3294，一道思路奇妙的Trie树题目
[SCOI2016]背单词题目传送门 前言参考这篇博客 题目大意输入 $n$ 个单词，要求我们给他进行重新排列，使得按以下规则花费最小 如果存在一个单词是它的后缀，并且当前没有被填入表内，那花费 $+= n*n$ ； 当它的所有后缀都被
2022-06-28 狂刷字符串
acm 字符串 Trie 树
牛客16638，一道比较经典的KMP题目 牛客16638，一道比较经典的KMP题目
carpet题目传送门 题目大意给出一个 $n * m$ 的字符矩阵，每个位置有一个 $cost$ ，找出这个矩阵的最小循环子矩阵 $p$ 行 $q$ 列，即最小二维循环周期，之后再找出每一个这样大小的子矩阵的 $cost$ 的最大值，再取
2022-06-27 狂刷字符串
acm 字符串 KMP