字符串 – Woshiluo's Notebook

AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖

2020年7月21日2020年12月16日 by woshiluo

我吐了，这题我写了两天……

考虑到我自己写的博客还没有 AC 自动机的，我会简单写一下

有一个说烂但是很形象的说法 Trie + KMP

AC 自动机用于多模式串匹配

就是你拿一个字符串，和一堆字符串

然后 AC 自动机可以让你快速的知道这一堆字符串中，那些是你这一个字符串的子串

2019年5月8日2019年5月8日 by woshiluo

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组用于解决各种玄学字符串问题，准确来说，它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

倍增法 (本博客所讲述) — $O(n \log(n))$
DC3 — $O(n)$
- DC3 虽然从复杂度分析的角度而言比倍增快，但配合各种常数问题，在信息学竞赛中反而容易被卡……
SA – IS 算法 — $O(n)$
- 可以参考这篇 Luogu 日报: https://www.luogu.org/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa

因为我太菜了，所以我就讲倍增求法