利用了 KMP 性质和 SAM 这一“数据结构”的特点并进行了动态维护。 题目描述 对于一个字符串 $S$,我们定义 $fail[i]$,表示最大的 $x$ 使得 $S[1..x]=S[i-x+1..i]$,满足 $(x<i)$。 显然对于一个...
KMP
CF955D Scissors 题解【KMP】【字符串】【贪心】
这道题是比较基础的KMP+特判问题。 Description Jenya has recently acquired quite a useful tool — \(k\)-scissors for cutting strings. They are generally used for cu...
洛谷 P4391 [BOI2009]Radio Transmission 无线传输 题解【KMP】【字符串】
一道比较简单的利用nxt数组的题。 题目描述 给你一个字符串,它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少。 输入输出格...
AC自动机 学习笔记【AC自动机】【字符串】【字典树】
AC 自动机是一种方便的多模式串匹配算法。基于字典树,用到了类似KMP的思维。 AC 自动机与 KMP 不同的是,AC 自动机可以同时匹配多个模式串,而复杂度不会达到太高。如果用 KMP 多次匹配字符串,复杂度就是 $O(k...
CF471D MUH and Cube Walls 题解【KMP】【差分】【构造】
一不小心看到了一句话题解就做出来了。感觉很浪费,把思路记录一下以后看。。。 Description Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the...
洛谷 P3193 [HNOI2008]GT考试 题解【KMP】【矩阵加速】【递推】
看出来矩阵加速也没看出来KMP…… 题目描述 阿申准备报名参加 GT 考试,准考证号为\(N\)位数\(X_1,X_2…X_n(0\le X_i\le9)\),他不希望准考证号上出现不吉利的数字。 他的不吉利数学\(A_1,A...
洛谷P2375 [NOI2014]动物园 题解【KMP】
一开始的方向应该对了,但是没有想到合理的优化还是没写出来…… 题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气...
KMP字符串匹配算法 学习笔记【KMP】【字符串】
一、简介 KMP是由Knuth、Morris和Prat发明的字符串匹配算法,它的时间复杂度是均摊\(O(n+m)\)。其实用Hash也可以做到线性,只不过Hash存在极其微小的难以避免的冲突。于是就有了KMP。 KMP算法...