目录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稀疏矩阵存储稀疏矩阵有两种存储方式①三元组存储②十字链表