题目：

给一个仅包含小写字母的字符串主串 S = abcacabdc，模式串 T = abd，请查找出模式串在主中第一次出现的位置；

对于这道算法题的解法，之前结束了BF算法和RK算法，BF算法是最好理解的，依次对比模式串和主串的各个字符，直到完全匹配，而RK算法解题，是将主串依次拆分为n个模式串长度的子串，并对其通过哈希算法换算成哈希值，进行比较。

而在利用BF算法解题时，会出现下面的情况：

假设主串S = abcababca，模式串T = abcabx，则会出现下面的比较

当比较到最后一个字符X时，不相等，则平移。 当进行到下面的比较时

发现前面两个对a 和b的比较是多余。

因此，可以定义一个数组next，数组的长度为模式串的长度，数组中来存储在进行匹配时，模式串标记j回溯的位置。如下图，直接从j = 3的位置开始比较。

而这就是KMP算法的原理。KMP算法主要是对模式串进行分析处理，依次找出模式串中相同的字符，当有相同字符的时候，j的回溯位置。而next数组的推导是KMP算法的关键。

第一种情况，模式串的字符都不相同时

假如：模式串T = abcdex，