CF1409F「Subsequences of Length Two」 1. 题目 题目链接：CF1409F「Subsequences of Length Two」 。 Description You are given two strings sss and ttt consisting of lowercase Latin letters. The length of ttt is 222 (i.e.i.e.i.e. this string consists on 2020-09-06 Technique ACM 题解 Technique ACM 题解
AC自动机 1. 简介 AC 自动机可以看作是字典树 + KMP，其主要构建步骤为： 将所有模式串插入字典树中，构建出字典树 BFS 字典树上所有的结点构造失配指针（同时考虑路径压缩） AC 自动机主要应用于多模式串匹配问题，即一个主串多个匹配的模式串问题。 2. 思想 AC 自动机基于字典树结构，将所有模式串插入字典树中，然后对字典树中的每个结点构造失配指针。AC 自动机中的失配指针与 KMP 中不同的 2020-09-04 Technique ACM 算法 字符串 Technique ACM 算法 字符串 算法 数据结构
AC自动机 1. 简介 AC 自动机可以看作是字典树 + KMP，其主要构建步骤为： 将所有模式串插入字典树中，构建出字典树 BFS 字典树上所有的结点构造失配指针（同时考虑路径压缩） AC 自动机主要应用于多模式串匹配问题，即一个主串多个匹配的模式串问题。 2. 思想 AC 自动机基于字典树结构，将所有模式串插入字典树中，然后对字典树中的每个结点构造失配指针。AC 自动机中的失配指针与 KMP 中不同的 2020-09-04 Technique ACM 算法 字符串 Technique ACM 算法 字符串 算法 数据结构
UVA12604「Caesar Cipher」 1. 题目 题目链接：UVA12604「Caesar Cipher」 。 Description In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widel 2020-09-04 Technique ACM 题解 Technique ACM 题解
UVA11452「Dancing the Cheeky-Cheeky」 1. 题目 题目链接：UVA11452「Dancing the Cheeky-Cheeky」 。 Description The Cheeky-Cheeky is a new song. They dance it in Mula, and also in Hong Kong. All the freekies dance it, and the geek all love it. And the 2020-09-04 Technique ACM 题解 Technique ACM 题解
UVA12467「Secret Word」 1. 题目 题目链接：UVA12467「Secret Word」 。 Description Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that Alicia chose. Alicia wrote a long string SSS in a piece of pa 2020-09-03 Technique ACM 题解 Technique ACM 题解
UVA455「Periodic Strings」 1. 题目 题目链接：UVA455「Periodic Strings」 。 Description A character string is said to have period kkk if it can be formed by concatenating one or more repetitions of another string of length kkk. For exampl 2020-09-03 Technique ACM 题解 Technique ACM 题解
前缀函数 1. 定义 1.1 前缀 & 真前缀 前缀是指从串首开始到某个位置 iii 结束的一个特殊子串。字符串 SSS 的以 iii 结尾的前缀表示为 prefix(S,i)=S[0..i]\begin{array}{c} prefix(S,i) = S[0..i] \end{array} prefix(S,i)=S[0..i] 真前缀指除了 SSS 本身的 SSS 的前缀。 1.2 后缀 &a 2020-09-03 Technique ACM 算法 字符串 Technique ACM 算法 字符串
前缀函数 1. 定义 1.1 前缀 & 真前缀 前缀是指从串首开始到某个位置 iii 结束的一个特殊子串。字符串 SSS 的以 iii 结尾的前缀表示为 prefix(S,i)=S[0..i]\begin{array}{c} prefix(S,i) = S[0..i] \end{array} prefix(S,i)=S[0..i] 真前缀指除了 SSS 本身的 SSS 的前缀。 1.2 后缀 &a 2020-09-03 Technique ACM 算法 字符串 Technique ACM 算法 字符串
KMP 1. 简介 KMP 算法是一种优秀的字符串模式匹配算法，相对于暴力匹配方法来说，其改进在于：每当一趟匹配过程出现字符比较不相等时，不需回溯主串的 iii 指针，而是利用已经得到的「部分匹配」的结果将模式串向右「滑动」尽可能远的一段距离后（即回溯模式串的 jjj 指针），继续进行比较。 2. 实现 设模式串为 p1p2⋯pmp_1 p_2 \cdots p_mp1p2⋯pm，主串为 s1s 2020-09-03 Technique ACM 算法 字符串 Technique ACM 算法 字符串