考场上唯一一道弃掉的题。看来 SAM 还是挺好玩的 题目背景 Yazid 和 Tiffany 喜欢字符串问题。在这里,我们将给你介绍一些关于字符串的基本概念。 对于一个字符串 $S$,我们定义 $|S|$ 表示 $S$ 的...
后缀自动机
51nod 1600 Simple KMP【KMP】【SAM】【树链剖分】
利用了 KMP 性质和 SAM 这一“数据结构”的特点并进行了动态维护。 题目描述 对于一个字符串 $S$,我们定义 $fail[i]$,表示最大的 $x$ 使得 $S[1..x]=S[i-x+1..i]$,满足 $(x<i)$。 显然对于一个...
洛谷 P3181 [HAOI2016]找相同字符 题解【SAM】【前缀和】
SAM 挺神奇的,就是不会.. 题目描述 给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。 输入格式 两行,两个...
洛谷 P4248 / loj 2377 [AHOI2013] 差异 题解【后缀自动机】【树形DP】
可能是一个 SAM 常用技巧?感觉 SAM 的基础题好多啊.. 题目描述 给定一个长度为 $ n$ 的字符串 $ S$ ,令 $ T_i$ 表示它从第 $ i$ 个字符开始的后缀,求: $$> \sum_{1\le i<j\le n}len(T_i)+le...
洛谷 P3975 / loj 2102 [TJOI2015] 弦论 题解【后缀自动机】【拓扑排序】
后缀自动机入门。 题目描述 为了提高智商,ZJY 开始学习弦论。 这一天,她在《String theory》中看到了这样一道问题:对于一个给定的长度为 $ n$ 的字符串,求出它的第 $ k$ 小子串是什么。你能帮帮...