一、串的概念

1、串的定义

太简单了就是代码里的字符串，跨专业的自己看下面图吧

2、串的操作

3、串的顺序结构

有这么四种方案，没什么好说的，哪怕是跨考的学一节应该也看得懂

4、串的链式存储结构

依旧没什么好说的，看一眼就行

二、开始有用的部分

专业术语【模式串】解释：

而这种在【主串】中找到某个和【模式串】匹配的【子串】，并返回该【子串第1个字符在主串的位置】的运算就叫——————【模式匹配】

1、朴素模式匹配算法

        没什么好说的，写过代码的应该看得懂下面图，就是【主串】取【和模式串一样长的子串】一一对比，一旦不同，【主串的子串】整体往后挪一位，又从头开始一一对比

        可以记一下，主串长度n、模式串长度m，看上面图主串里的【子串的头】最多移动到【n-m+1位】，也就是最多对比【n-m+1】个子串

；

；

然后简单记一下代码逻辑：

• 1、遍历【主串的指针i】和【遍历模式串的指针j】初始位置都是0
• 2、若某一位匹配失败，因为i和j都是对应子串相对一样的位置，那么：
  • 【i】就应该等于【i-j+2】，因为：
    • 【i-j】就是回到主串的【当前子串】的开头前一位
    • 【i-j+1】就是回到主串的【当前子串】的开头第一位
    • 【i-j+2】就是回到主串的【当前子串】的开头前二位，那么就可以以他为【下一个子串的开头第一个元素】
  • 而【j】直接等于1，回到自己模式串的开头第一位即可
• 3、而如果找到了主串中【匹配模式串的子串】
  • 那就很简单，返回【这个子串第一个字符的位置】

；

• 朴素模式匹配算法【时间复杂度】

  • 主串长度n、模式串长度m，【时间复杂度：O(n*m)】
    • 主串需要最多对比【n-m+1】个子串，就是近似n*m

【例题】

2、KMP算法

这玩意太几儿抽象了，必须先从人类视角解决概念，然后再讲具体实际程序运行是怎样的

1）纯抽象概念解释

为了弥补朴素模式匹配算法太慢，KMP算法实现了线性的时间复杂度

【首先先不考虑计算机，仅从人的视角出发】：

• 主串与模串对比时，出了【不匹配的字符】时，应从【主串】的【当前指针 的 前面】找到一个“最长后缀”、从【模式串】的【当前指针 的 前面】找到一个“最长前缀”
  • 注意：
    • 1、是指针的前面的串，不包括指针指向的这个字符
    • 2、【前缀】不包括该字符串最后一位字符、【后缀】不包括该字符串第1位字符
    • 3、不管前缀、后缀，都要和原字符串保存一样的字符顺序
  • 当找到一个【相同】并且【长度最长】的【主串的“前缀”】和【模式串的“后缀”】，那么这小子串就叫【最长相同前后缀】
• 找到【最长相同前后缀】之后
  • 【主串】指针不要动！！！！！
    • KMP的目的就是不要让 “匹配出错时，主串回溯又去对比已知正确的部分”，如果主串前面无法和模式串匹配的话，指针根本不可能走到后面！！！
    • 也就是说，当前指针指向的这个不匹配字符，前面的部分100%是跟模式串当前指针前面的字符一模一样的
  • 每次出错只动【模式串】指针！！！！
    • 规则：让指针回退到刚刚找到的【最长相同前后缀】的【后一位】
    • 也就是模式串【自己的最长相同前缀】的【后一位】这里我画了两个图，我们可以发现其实按人类理解方式，我们可以用最简单的逻辑理解：【就是把模式串整体 右移】，而且刚好【模式串前缀AB】移动到了【模式串后缀AB】的位置，而指针就在【模式串前缀AB】后1位
• 对于上面的过程，我们仔细观察可以总结一些【规律】
  • 出现匹配不一样的字符时，【主串指针前内容】=【模式串指针前内容】
  • 由上面的结论可知，其实所谓【主串的 “最长相同后缀”】不也可以用【模式串的 “最长相同后缀”】吗
  • 所以最简单的原理总结：KMP就是让【模式串】的【自己的前缀】找【自己的后缀】

2）计算机数组逻辑

那么人类是可以判断出【最长相同前后缀】是哪个，但是计算机应该如何让模式串找到这个【最长相同前后缀】的【后一位】？

；

【next()数组 统计大法】

• ① 多加一个【next数组】用来统计模式串【每一位出现不匹配】时，对应的【指针应该跳到哪？】
• ② 而【next数组】里的数值的本质就是：记录模式串里，每一位字符【前面】的【最长前后缀长度】+【1】

  大概流程就是下图这样：

  对应的结果：

• KMP模式匹配算法【时间复杂度】：

  • 主串长度n、模式串长度m，【时间复杂度：O(n+m)】
  • 主串只用一次性遍历一次，记住了是线性时间复杂度！！

3）实际做题方法（两种方法包教会）

【强烈推荐！！！这个方法是最快最简单的，懂原理一切都简单】

如果前面我说的逻辑你能理解看懂，那么这里计算【next数组】就很简单：

• 我们以模式串【a b a a b a c a】为例子
• 【next数组】计算方式如下（这个是next数组的值是按从1开始的位序的）
• 换成从0开始的数组形式，next数组只需要把所有值-1即可：

【不太推荐，非常绕，实在是没招了你可以用这个方法......】

如果前面的原理你啥也看不懂！！！！那么没关系！！！！现在我们可以按下面方式来：

• 1、首先，在得出【next数组】时，我们还需要设置一个【PM数组】，别问为什么，我也不知道，你只用知道你考试做题就按这个步骤来
• 2、【PM数组】对应统计【模式串的每一位】前面的【最长相同前后缀】的【长度】
  • 听不懂没关系，完全没关系，看流程照做就行
  • 【第一步】：模式串第一位一定是0，什么都别管直接写0就行了
  • 【第二步】：第1位和第2位对比，一样的话，第2位的值是0；不一样则第2位是0
  • 【第三步】：接下来【指针 j：指向第1位】、【指针 i：指向第3位】，它两开始正常同步往后遍历
    • 如果【模式串[i] == 模式串[j]】：那么 i连起来的字符串 和 j连起来的字符串 一直一样，那就【PM[i] = PM[i-1]+1，统计相同最长前后缀长度】就行，也就是一直累加
    • 如果【模式串[i] != 模式串[j]】：那么【i 不要动！！】，【指针 j直接回头重新遍历】
      • 直到【指针 j 】找到【模式串[i] == 模式串[j]】的字符，那么这个字符对应的PM是什么值，PM[i]就等于它+1，即【PM[i] = PM[j] + 1】如果【模式串[j]】一直遍历到【模式串[i-1]】，还是没有找到【模式串[i]==模式串[j]】的字符，那就让【PM[i]==0】
• 3、得出了【PM数组】后，再变两步就可以得到【next数组】了：
  • 首先：把PM整体右移1位，第一位写-1
  • 最后：整体每一位都+1，得到next数组（最后一位记得舍去就行了）
  • 别问为什么，我有点懒得剖析它的原理了。。。老子只是考试狗而已
    • 另外我这是为了写清楚给大家看，考试做题大家画一个数列在上面涂涂改改就行了，不用像我这样写这么清晰的步骤
    • 【另外】上面是字符串以【1为开头】的情况，如果是以【0为开头】的话，那PM转化成【next数组】时只需要【右移 + 开头补上-1】到这一步就够了！！！

3、KMP优化算法

那么还有一种【next数组】Pro升级星耀版！！！————【nextval数组】！！！

1）【nextval数组】原理

【next()数组】虽然很牛，但是还有一丁点缺陷可以被优化：

• 我们会发现像下面例子这样，当【主串】和【模式串】对比到第4个字符，【模式串】的字符【A】不能和主串匹配，需要回退
• 根据前面教的（记住【模式串前缀找后缀】），那么指针会回退到第1个【A】，这一步没问题
• 但是，我们刚刚匹配失败的时候，已经知道【模式串第4个A】不能与主串的B匹配，现在回退到【模式串第1个A】.........不还是【A】吗？我们干嘛又用【A】与主串B对比一遍？？？
  • 那么现在问题就是：如果出现【匹配失败的字符】和【模式串指针应回退到的字符】一样的时候，就相当于多做了一次无用功对比，完全没必要！
  • 那么怎么生成【nextval】数组？规则如下图：这里原理看不懂没关系，我们计算题的时候不会用上面的方法来计算，很乱，我下面写了更好的流程

2）实际做题方法

我们需要知道原理吗？不需要！！写代码用不上！考试狗应试教育更用不上！！！

所以直接讲步骤怎么求得【nextval数组】：

• 【第一步】：把刚刚求出的【next数组】抄在模式串下
  • 然后给模式串列出【位序号（从1开始）】
  • 然后在【next数组下】把【每个值】对应的是【模式串的哪个序号的字符】列在下面，得出一个【新的字符串（第1位不用写，空着）】
    • 注意：【next】数组要用【还未-1】的那个版本（也是PM右移后+1那个版本）
• 【第二步】：然后把【新字符串】个【模式串对比】
  • 从【新字符串】第2位开始，找出所有【和模式串不一样的字符】！！！再三强调！！！是【不一样的】！！！！
    • 直接把不一样的这些字符对应的【next数组的值】照抄到下面，作为【nextval】当前位的值
  • 然后【nextval数组】的【第1位】依旧跟【next数组】一样，默认是0
  • 然后【新字符串】里剩下【和模式串一样的字符位】，我们看上面【 next[i] 】，按从1开始的位序，找到【 nextval[ next[i]-1 ] 】的值，就是【nextval[i]的值】
    • 即【 nextval[i] = nextval[ next[i]-1 ] 】！！！！！！！！！
    • 而且强调，【nextval数组】也是从1开始

【例题】

懒得写了，剩下例题用我的讲解完全会做。。。。。。。