Daowuu

字符串

动态规划(1) 博弈论(1) 图论(9) 数学(10) 数据结构(3) 未归档(1) 计算几何(8) 题解(2) 高精度(1)

/ 注册

全部文章 / 字符串（共5篇）

AC自动机来自专栏

#AC自动机时间复杂度： AC自动机是多模匹配算法，能在一个文本串中同时查找多个不同的模式串。注： “fail指针” 、 “蓝色虚点” #include<bits/stdc++.h> using namespace std; const int maxn = 4e5+1; /...

字符串

2020-08-20

0 800

字典树来自专栏

字典树（前缀树）具体来说，Trie一般支持两个操作： insert(S)：插入操作，就是将一个字符串 S 加入到集合中。 search(S)：查询操作，就是查询一个字符串 S 是不是在集合中。 int trie[maxn][26], tot; // 字典树 & 前缀树 int ex...

字符串数据结构

2020-08-01

0 680

Manacher 来自专栏

manacher（马拉车）算法时间复杂度求解一个字符串的最长回文子串长度的问题。注：先插入 n+1 个 # ，再设置一个 po，维护已知区域 (po-Next[po]，po+Next[po])，即维护 po。 char s[maxn], t[maxn<<1]; // s 为文本串...

manacher 字符串

2020-08-01

0 422

KMP 来自专栏

KMP KMP 是单模匹配算法，即在一个长度为 n 的文本串中查找一个长度为 m 的模式串。 KMP 算法的基础时间复杂度在用 KMP 算法时，指向 s 的 i 指针不会回溯，而是一直往下走到底。那么 KMP 是如何让 i 不回溯，只回溯 j 的呢？这就是 KMP 的核心———fail[]数组...

kmp

2020-07-29

0 769

序列自动机来自专栏

序列自动机序列自动机是一个可以快速判断字符串t是否是字符串s的子序列的一个算法。序列自动机基础初始化：对s构造序列自动机，使用代表从第i个位置开始，字符j出现的第一个位置。我们倒着遍历更新即可。 const int maxn = 1e6+1; const int inf = 0x3f3...

字符串序列自动机

2020-07-24

0 564