主串与模式串的匹配
（1）BF算法：
BF算法比较简单直观，其匹配原理是主串S.ch[i]和模式串T.ch[j]比较，若相等，则i和j分别指示串中的下一个位置，继续比较后续字符，若不相等，从主串S的下一个字符（i=i-j+2）起再重新和模式串T的第一个字符（j=1）比较。
（2）KMP算法：
KMP算法相对BF会复杂一些，但对于计算机而言，这其实是减少很多不必要的匹对。在匹配失败时最大的移动模式串，以减少匹配次数，即当匹配失败时（S.ch[i]!=T.ch[j]），在模式串中已匹配的字符找出其长度最长的相同前后缀，假设其长度为k，则模式串T回溯到T.ch[k+1]与S.ch[i]匹对。
| 模式串 | 前后缀 | 相同个数 |
| a | 无 | 0 |
| ab | 无 | 0 |
| aba | a | 1 |
| abab | a、ab | 2 |
| ababa | a、ab、aba | 3 |
在作业题中，我用的是KMP算法进行匹配。考虑的当模式串第一位字符与主串字符不匹配时，若按原方法回溯会陷入死循环，所以讲next[0]初始为-1
定义晚next函数后则定义KMP函数，仅需匹配时i++和j++，不匹配时i不变，j=next[j]（将模式串回溯至k）重新开始进行匹配，直至匹配完成输出i-j+1（主串中的子串的第一个字符所在位置）
原文：https://www.cnblogs.com/llhs/p/10703167.html