Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共7篇）

最小表示法

用途给一个首尾相连的字符串，找一个位置，从这个位置往后形成一个字符串，使字符串的字典序最小算法定义三个指针\(i=0\),\(j=1\),\(k=0\)，\(i\)和\(j\)是当前判断的位置，\(k\)是相同的串的长度，表示\(str[i...i+k]\)和\(str[j...j+k]...

算法字符串

2019-02-24

0 566

Manacher算法详解

问题什么是回文串，如果一个字符串正着度读和反着读是一样的，这个字符串就被称为回文串。 such as noon level aaa bbb 既然有了回文，那就要有关于回文的问题，于是就有了—— 最长回文子串：给定一个字符串，求它的最长回文子串长度。暴力找出所有的子串，遍历每...

算法字符串

2019-03-02

0 830

后缀数组详解

##基本概念 ###什么是后缀假如你有一个字符串如 "gzyorz" 它的后缀是 "gzyorz"，"zyorz"，"yorz"，"orz"，"rz"，&q...

字符串数据结构

2019-03-12

0 700

Nikitosh 和异或(trie树)

题目： #10051. 「一本通 2.3 例 3」Nikitosh 和异或解析：首先我们知道一个性质\(x\oplus x=0\) 我们要求\[\bigoplus_{i = l}^ra_i\]的话，相当于求\[(\bigoplus_{i = 1}^la_i)\oplus (\bigoplu...

字符串 trie树

2019-07-29

0 589

The XOR Largest Pair(tire树)

题目 The XOR Largest Pair 解析一年前听学长讲这道题，什么01trie，好高级啊，所以没学，现在一看。。。。看到xor就应该想到二进制，一看数据\(A_i< 2^{31}\)，考虑把所有的数都处理成长度为32的二进制数，插入字典树中，查询的时候就逐位比较，有不同的...

字符串 trie树

2019-07-27

0 596

P3121 [USACO15FEB]审查(AC自动机)

题目： P3121 [USACO15FEB]审查（黄金）Censoring (Gold) 解析：多字符串匹配，首先想到AC自动机建立一个AC自动机因为有删除和拼接这种操作，考虑用栈维护顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走...

AC自动机字符串

2019-07-29

0 510

The Xor-longest Path(trie树)

题目： #10056. 「一本通 2.3 练习 5」The XOR-longest Path 解析：做完#10051后就不是很难了继续利用异或的性质有\(dis(u,v) = dis(1,u)\oplus dis(1,v)\) 把边权放到点上，然后字典树求最大异或值代码 #inclu...

trie树字符串

2019-07-29

0 654