文章目录
第二节 串
串的基本概念
C语言中没有字符串类型，而是提供了字符数组，将字符串作为字符数组来处理。当使用字符数组表示一个字符串时，C语言规定使用一个字符串结束标志"\0’表示串的结尾。同时，C语言还提供了许多字符串操作。例如，可以定义字符串s1和s2，并展示其内容和长度，语句如下。
串的模式匹配
求在主串中寻找子串(第一个字符)在主串中的位置，称为串的模式匹配。
此时，子串又称为模式，:串又称为目标。
例如，目标T=“Beijing”，模式P=“jin”，匹配结果为3。
朴素的模式匹配算法(BF算法)
分别从主串与模式串各自的首字符(看作当前位置)开始，依次比较两个串的当前字符。如果相等，则两个串各自的当前位置均后移一个位置，继续比较下对字符;如果不等，则模式串整体后移一个位置，模式串的首字符和主串的第二个字符分别是当前位置,依次比较两个串的当前字符。继续这个过程，当主串与模式串失配时，模式串整体后移一个位置，从模式串的首字符和主串的第三个字符、第四个字符等开始，依次比较两个串的当前字符。直到模式串与主串的某个子串完全匹配，或到达了主串的最后位置，仍未找到与模式串完全匹配的子串时为止，前者表示匹配成功，后者意味着匹配失败。
全称 Brute - Force 算法 ，也被称为暴风算法、简单匹配算法、蛮力算法 。这是一种在数据结构中用于字符串模式匹配的基本算法，常用于在一个主串内查找一个子串的出现位置，其核心思想是穷举法。
第一趟比较时，模式串前两个字符分别与主串的前两个字符匹配成功，但第三对字符失配。带下画线的字符表示每趟匹配时失配的位置。失配后，模式串整体后移一个位置，再次从它的首字符开始与主串相对应的字符进行比较。这个过程一直进行到第四趟，匹配成功。在每趟匹配中，主串与模式串的字符之间的比较次数均有三次，共四趟，所以共进行了12次比较。
算法最坏时间复杂度O(n x m)
朴素的模式匹配算法简单，但时间效率不高。设主串长度为n，模式串长度为m。如果每次都是比较到模式串最后一个字符时才出现失配，且主串的最后m个字符与模式串匹配成功(与例4-8中的情形类似)，就出现了最坏情况。
此时，每一趟都进行了m次比较，共比较了n-m+1趟，故总比较次数将达到(n-m+1)xm。
在多数场合下，m远小于n，因此，算法的最坏情况时间复杂度为O(n x m)。
- 和排列组合有关，选一个最简单例子，然后推广
改进的模式匹配算法(KMP算法)
有多个模式匹配算法改进了BF算法，下面介绍经典的KMP算法。
在BF算法中，当失配时，模式串整体后移一个位置并继续从模式串首字符开始进行比较。在多数情况下，主串和模式串的当前位置都要回退，意味着主串和模式串中的字符都要进行多次比较，故算法的效率不高。
实际上，当模式串整体向右移动一位后，失配位置之前的各对字符都已经比较过了，也就是已经知道这几个位置上主串和模式串的字符是匹配的。
因此，可以借助前一趟比较的结果，决定本趟匹配时模式串后移的位数，从而提高匹配的效率。这种处理思想是由D.E.Knuth、J.H.Morris和V.R.Pratt同时提出的，相应的算法称为KMP算法。
特征向量next，来确定k值
特征向量next的算法实现
算法最坏时间复杂度O(n)
进一步改进next值的计算，简化步骤
第四章真题
真题1
1、初值表p，矩阵表示如图，更加清晰，实际上是同一条件的不同表示，这种更加容易让人理解
2、要求解的东西，是矩阵的行、列坐标，注意是从0开始，p后面的坐标表示位置1的行，实际上是第2行，位置2的列，实际上是第3列，为0，选A，这个是输入值的不同表示，变成矩阵形式则一目了然，
其实关键是这种哲学上的条件翻译，以及关于坐标位置和实际第几个位置的哲学辨析，翻译出来之后，求解简直一目了然
- 为什么能够这样翻译，问问AI，或者自己先记一下，关键还是多找这种条件题目
真题2
位置0的第一个元素，a0-0，地址100
第二个元素，是a1-0，；看来这个的地址是104呗，每个元素占4个地址
第三个元素，是a1-1，地址108
a4-4，已经是第十五个元素
| 位置0 | 位置1 | 位置2 | 位置3 | 位置4 | 位置5 | ||||
|---|---|---|---|---|---|---|---|---|---|
| 位置0 | 第一个100 | ||||||||
| 位置1 | 二104 | 三108 | |||||||
| 位置2 | 四 | 五 | 六 | ||||||
| 位置3 | 七 | 八 | 九 | 十 | |||||
| 位置4 | 十一 | 十二 | 十三 | 十四 | 十五 | ||||
| 位置5 | 十六 | 十七 | 十八 | 十九 | 二十 | 二十一 | |||
（技巧：位置，角标，采用阿拉伯数字，把第几个元素，不要用阿拉伯数字，免得数字看来看去弄混！）
- 再进阶一点，可以找找这个排列的计算公式，简单粗暴一点就直接排，反正不超过10*10的矩阵
重点是明晰下三角矩阵，这个概念的图的元素的顺序位置
以及进一步明晰，这个概念图的元素的坐标标号
一、然后直接翻译和记忆，a1-1是第几个元素，a0-0是第几个元素；已经输入值，a4-4是第几个元素
二、1、再解题步骤，通过元素位置之差，先求出单个元素占用位置
2、第三个元素，100加了两个4
第十五个元素，100加十四个4，就是156，选B
注意别算成加十五个4了，所以还是图示最简单，找解题规律一目了然
- 先别管什么偏移量，存储单位的概念，直接画图最直观明了
