数据结构与算法串的模式匹配

1.简单的模式匹配算法
子串的定位通常称为串的模式匹配，它求的是子串的（常称模式串）在主串中的位置

实现思想：
将主串中与模式串长度相同的子串摘出来，按个与模式串对比

缺点：主串指针会出现回溯现象导致时间开销增加

最坏时间复杂度：O(mn)，其中m和n分别代表主串和模式串的长度

2.KMP算法
字符串的前缀、后缀和部分匹配值

next数组：当模式串的第j个字符匹配失败时，令模式串跳到next[j]再继续匹配

时间复杂度：O(m+n)

优点：主串不会进行回溯

3.KMP算法优化
当子串和模式串不匹配时j=nextval[j],通过构造nextval函数