数据结构：第5讲：字符串、数组

目录

1.字符串匹配
2.多维数组

---

1.字符串匹配

1.1 KMP匹配

（1）思路：

基于模式串确定next数组，利用next数组完成字符串匹配，在匹配过程中，发生字符不匹配情况时，next数组用来帮助确定下一次的匹配位置。

（2）

①

②如何确定next数组

遍历模式串，获取每个字符前面的内容，根据前面内容的前、后缀中相同内容的最大长度填写next中的值。

注：前面没有内容就填写-1。

注：若前面的内容只有一个字符，一个字符不能既看成前缀，又看成后缀，所以一个字符看成没有前缀和后缀。所以填写0。

③如何使用next数组

下标为5匹配失败，去next数组找下标5的元素，发现是2，将模式串中下标为2的元素与字符串中下标为5的元素进行对齐，然后继续匹配。

注：以此题为例，第二次匹配时，从模式串中下标为2的元素开始与字符串进行匹配。

2.多维数组

2.1 二维数组

（1）按行优先在内存中存储

（2）按列优先在内存中存储

（3）例题

2.2 特殊矩阵

（1）对称矩阵

（2）上三角矩阵

（3）下三角矩阵

（4）三对角矩阵

（5）稀疏矩阵

存储稀疏矩阵有两种存储方式：

①三元组存储

②十字链表