bzoj 4641 基因改造

Posted by

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=4641

题解

我们发现对于两个串匹配所依赖的信息只是相同字符之间的相对位置,也就是一个字符和它上一个相同字符的距离,于是考虑以这个信息建立新的字符串,这样两个字符串就可以直接KMP了;

然而对于第一次出现的字符,将它在新串中的值赋为\(-1\),KMP的时候需要特殊考虑。

(妈耶我快不会打KMP了……)

代码

2 comments

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注