【学习笔记】AC 自动机

By Zepto in Study on

听老师说 AC 自动机不算自动机啊，因为 Wikipedia [https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm] 上的说法也是 $Aho–Corasick algorithm$ 而不是 $Aho–Corasick Automaton$. 然鹅既然大家都这么叫了我标题也就这么起喽 or2 原理 和往常一样，先坑着。。。 例题 模式串匹配 先上个洛谷模板 [https://www.luogu.org/problemnew/show/P3808] 的代码。题目很裸（毕竟是简单模板），给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。 代码 #include #define ll long long #define…

【学习笔记】线性基

By Zepto in Study on

原理 坑。 例题 P哥的桶 首先有一道很水的例题 [https://www.luogu.org/problemnew/show/T37302]。 题意 一共有 n 个数组，可以向某一个数组里增加一个数，或者询问区间内所有数组里数组可能的最大异或和。 思路 线性基套上一个线段树，可以学习一下基本插入和查询操作。 #include #define maxn 50001 #define maxl 32 #define ll long long #define ls (p<>1) using namespace std; struct LB{ ll a[maxl+1]; void reset(){ memset(a,0,…