Day37-【13003】短文，串的基本概念，匹配算法，算法时间复杂度，真题训练

文章目录

- 第二节串
- - 串的基本概念
  - 串的模式匹配
  - - 朴素的模式匹配算法(BF算法)
    - - 算法最坏时间复杂度O(n x m)
    - 改进的模式匹配算法(KMP算法)
    - - 特征向量next，来确定k值
      - 特征向量next的算法实现
      - 算法最坏时间复杂度O(n)
      - 进一步改进next值的计算，简化步骤
- 第四章真题
- - 真题1
  - 真题2

第二节串

在这里插入图片描述

串的基本概念

在这里插入图片描述

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	十六	十七	十八	十九	二十	二十一