苟且的狮子的博客

A Simple Problem

kmp、差分约束题意：分析第一个要突破的点在于：如何表示认错树木的现象。我们可以暴力地枚举记忆中的p字符串，然后再用kmp进行匹配但是很明显这会超时！所以我们需要采取其他的办法。进行分辨。这里我们使用的技巧叫做差分约束！通过记录当前p[i]出现的位置与其上一次出现位置的差值，来限制数目的...

Just A String

kmp 题意：分析：这一题，我最初很没思路。刚开始想会不会是kmp扩展，但是琢磨一番发现无法解决。然后，在进行手工推算时，发现这是个kmp问题。请看：题目让我们求的是：对于字符串s,判断他的每一个前缀和每一个后缀的B是否？从题目所给的数据量来看，我们很简单就能想到枚举。但是，即便枚举我们...

字符串的问题

kmp 题意：分析：我们看着一题，我们仔细想想。首先如果没有要求中间子串的话，就很简单了。我们直接输出前后缀相等的就好了。无论是 kmp 还是暴力都是线性时间。但是麻烦就在于中间要有字串。那我们想想，如何判断中间有没有子串呢？假设，next[n] = k 意味着s0,s1,s...