利用了 KMP 性质和 SAM 这一“数据结构”的特点并进行了动态维护。 题目描述 对于一个字符串 $S$，我们定义 $fail[i]$，表示最大的 $x$ 使得 $S[1..x]=S[i-x+1..i]$，满足 $(x<i)$。 显然对于一个...

     这道题是比较基础的KMP+特判问题。   Description Jenya has recently acquired quite a useful tool — \(k\)-scissors for cutting strings. They are generally used for cu...

      一道比较简单的利用nxt数组的题。   题目描述 给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少。   输入输出格...

AC 自动机是一种方便的多模式串匹配算法。基于字典树，用到了类似KMP的思维。 AC 自动机与 KMP 不同的是，AC 自动机可以同时匹配多个模式串，而复杂度不会达到太高。如果用 KMP 多次匹配字符串，复杂度就是 $O(k...

      一不小心看到了一句话题解就做出来了。感觉很浪费，把思路记录一下以后看。。。 Description Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the...

      看出来矩阵加速也没看出来KMP……   题目描述 阿申准备报名参加 GT 考试，准考证号为\(N\)位数\(X_1,X_2…X_n(0\le X_i\le9)\)，他不希望准考证号上出现不吉利的数字。 他的不吉利数学\(A_1,A...

      一开始的方向应该对了，但是没有想到合理的优化还是没写出来……   题目描述 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气...

一、简介     KMP是由Knuth、Morris和Prat发明的字符串匹配算法，它的时间复杂度是均摊\(O(n+m)\)。其实用Hash也可以做到线性，只不过Hash存在极其微小的难以避免的冲突。于是就有了KMP。       KMP算法...