ACM 选手带你玩转 KMP 算法！ _匹配

大家好伐，我是侬们的。
今天来学能让小儿止啼的 KMP ，是不是很慌？
本来在本蛋的计划里， KMP 的顺序还是要往后放一下，但是架不住小婊贝催问。
那还说啥，直接安排！就今天，直奔字符串模式匹配！
你们的需求就是我肝的方向！上面的小老弟留言一次哪成，看着不像铁蛋粉
这次保证安排的明明白白的，文章除了理解 KMP 算法的本质，拿去应付考试题也保证妥妥的！
字符串模式匹配是字符串中最重要的操作之一，就是找模式串在主串中的位置。
臭宝：呃，啥是主串，啥是模式串咧？
蛋蛋：如果你要找字符串 B 在字符串 A 中的位置，那么字符串 A 就是主串，字符串 B 就是模式串。可以理解主串就是大串，模式串就是小串。
字符串模式匹配算法有很多，但是要说提起字符串匹配，大家脑阔里的第一反应还是看毛片，呃， KMP 算法。
KMP 算法匹配字符串非常高效，但是原理有些复杂，学起来脑瓜子嗡嗡的，是学生时代学数据结构与算法绕不过去的坎儿。
不过不慌，这玩意本帅蛋门儿清。掏出你的卫生纸，呃，草稿纸，整活。
要学 KMP 模式匹配算法，首先先明白之前的匹配有多笨，所以我们先来看无脑流暴力匹配。
暴力模式匹配
暴力模式匹配，无脑流的典型代表，没办法情况下的无冕之王。
假设主串的长度为 n ，模式串的长度为 m ，暴力模式匹配就是对主串的下标为 0 1 2 3 ... n - m 的元素作为模式串的开头，与模式串依次进行匹配，看有没有与模式串完全匹配的。
下面来看一个例子。
从上图可以看出，暴力匹配是在主串的长度下做模式串次匹配。
最好的情况就是从第 1 次开始就匹配成功，此时的时间复杂度就是 O(1) 。
最坏情况的情况是，模式串每次都匹配到最后一个才发现和主串不同。比如主串是“” ，模式串是“aab” 。
看上图，除了最后一次，其余的都是每次匹配到最后，才发现，啊，我们不一样。
这种情况下，上图中，模式串在前 3 次，每次都要匹配 3 次，并且不匹配，直到第 4 次，全部匹配，不需要继续移动，所以匹配的次数为（6 - 3 + 1）* 3 = 12 次。
由此可知，对于主串长度为 n ，模式串长度为 m ，最坏情况下的时间复杂度为 O((n - m + 1) * m) = O(n * m) 。
你看，暴力模式匹配这么低效，你能忍的了？
忍不了吧，来，看毛片！
KMP模式匹配
KMP 算法全称，是由 D.E.Knuth、J.H. 和 V.R.Pratt 三位大佬一起捣鼓出来的。
KMP 算法目的是为了快速的从主串中找到模式串，强调的是快，那咋快的呢？
那肯定是去掉暴力模式匹配中的”无脑“的部分。
上图是暴力模式匹配的前 2 步，有比较指针 i 和 j 。
可以看到，在第 1 次匹配的时候，比较指针 i 和 j 走到了下标为 5 的位置发现不匹配的元素，然后进行第 2 次匹配，此时 i 回到了下标为 1 的位置。