刷题记-IV

前言

关于KMP算法，个人理解不深不透彻，通过几道题的训练，理解程度+0.01%，虽然本人不叙述整个算法的原理，但倒是可以推荐几篇博文给大家

KMP详解

https://www.cnblogs.com/zhangtianq/p/5839909.html

KMP 循环节

https://www.cnblogs.com/chenxiwenruo/p/3546457.html

剪花布条 | HDU - 2087

思路

裸的KMP算法

Oulipo | HDU - 1686

题目大意

给定W串和T串，求T串中有多少个W串，允许重叠

思路

也是裸的KMP算法，难点就在于允许重叠，其实只需要在匹配完成一次后 j = knext[j]，移动到前缀就可以了

Cyclic Nacklace | HDU - 3746

题目大意

给定一字符串，问需要添加几个字符才能使得整个串由某一个不为本身的子串循环构成

思路

真的是有些感叹next数组的博大精深，具体思路其实可以看第二篇博文，写得蛮清楚的