串

0个或多个任意字符组成的有限序列称为串

子串

串中任意个连续的字符称为该串的子串（包括空串）

子串位置

子串第一个字符在父串中的位置

空格串

由空格字符组成的串

串的链式存储结构

由于串的单个字符占用空间小，所以一个节点只存储一个字符的话，存储密度太低，故而一个节点存储多个字符

串的匹配-KMP算法

BF算法，是指经典的循环遍历方法，复杂度为O(n*m)

KMP算法是一种牺牲空间来加快速度的算法

https://zhuanlan.zhihu.com/p/83334559这篇文章讲的很清楚，有时间整理一下

简单来说，kmp算法先构建出一份图谱来确定不同状态前进或者回退，以及回退多少步。

数组

二维数组

数组中套娃数组，形成二维数组。

二维数组的逻辑结构

  • 线性结构：每个元素是定长的数组
  • 非线性结构：每个元素既在行表中，又在列表中。

二维数组的存储结构

以行序为主序

a[i][j]的位置在LOC(i,j)=LOC(0,0)+(n*i+j)*L

矩阵的存储

常规存储：存储为二维数组，不适合稀疏矩阵，相同值过多的矩阵

压缩存储：对数据有规律的矩阵，可以针对特性，进行压缩存储