4.模式匹配
4.1概述
串的查找定位操作，也称为串的模式匹配操作。
主串：当前串，长度用n表示。
模式串：在主串中需要寻找的子串，长度用m表示。
模式匹配特点：
匹配成功，返回模式串的首字母在主串中的位序号（索引号）。
匹配失败，返回-1
模式匹配的常见算法：
Brute-Force算法：蛮力算法，依次比较每一个，比较次数多，时间复杂度O(n×m)
KMP算法：滑动算法，比较的次数较少，时间复杂度O(n+m)
4.2Brute-Fore算法：分析
第一趟：运行后的结果
第一趟过渡到第二趟
第二趟不匹配，直接过渡到第三趟
第三趟： 
第三趟过渡到第四趟
总结：核心算法（找主串的下一位）
4.3Brute-Force算法：算法实现
/** this 主串 * @param t 模式串 * @param start 在主串中开始位置，例如：indexOf_BF("abcabc", 0) */ public int indexOf_BF(IString t, int start) { // 0.1 非空校验 if(this == null || t == null) { //0.1 主串或模式串为空 return -1; } // 0.2 范围校验 if(t.length() == 0 || this.length() < t.length()) { //0.2模式串为空或比主串长 return -1; } int i = start , j = 0; // 1 声明变量 while( i<this.length() && j<t.length() ) { // 2 循环比较,主串和模式串都不能超过长度 if(this.charAt(i) == t.charAt(j)) { // 2.1 主串和模式串依次比较每一个字符 i++; j++; } else { // 2.2 当前趟过渡到下一趟 i = i - j + 1; // 2.3 核心算法：主串中下一字符 j = 0; // 2.4 模式串归零 } } // 3 处理结果 if(j >= t.length()) { //3.1 模式串已经循环完毕 return i - t.length(); //3.2 匹配成功，第一个字母的索引号 } else { return -1; //3.3 匹配失败 } }
4.4KMP算法：动态演示
- 核心思想：主串的指针i不会回退，通过
滑动模式串进行匹配。
滑动的原则：可以从最大公共前缀，直接跳到最大公共后缀。
- 思考：ababa 最大公共前后缀是？
最大公共前缀：==aba==ba
最大公共后缀：ab==aba==
- 第一趟：i 从 0-->2
遇到不匹配的数据时，需要移动模式串，当前公共部分是“ab”，没有最大公共前后缀。模式串从头开始 
第二趟：i 从 2 --> 7
- 遇到不匹配的数据时，需要移动模式串，当前公共部分是“abcab”，有最大公共前后缀
第三趟： i=7 位置数据不一致
遇到不匹配的数据时，需要移动模式串，当前公共部分是“ab”，没有最大公共前后缀。模式串从头开始 
第4趟：数据不一致，i 7 --> 8 ， j 归零 
第五趟：i从8 --> 13
4.5KMP：求公共前缀next数组--推导
当我们准备求公共前后缀时，主串和模式串具有相同的内容，所以只需要看模式串。
实例1：模式串："abcabc"
提前将模式进行处理（预判）：将每一个字符假设不匹配时，公共前后缀提前记录下来，形成一个表格。
第一个位置：-1
第二个位置：0
使用next数组，记录统计好的表格。
实例2："ababaaa"
实例3：“ababaab”
4.6KMP算法：求公共前缀next数组--算法演示
实例1：模式串："abcabc"
第三位的数值
第四位的数值
第五位的数值
第六位的数值
处理完成
实例2："ababaaa"
第三位的值： k == 0
第四位的值：字符相等
第五位的值： 字符相等
第六位的值：字符相等
第七位的值：字符不相等，且k!=0
- 字符不相等，k!=0，移动k
字符不相等，k!=0，再移动k
字符相等
处理完成
4.7KMP算法：求公共前后缀next数组--算法
/** 获得next数组 * @param T 模式串 * return 返回next数组 */ public int[] getNext(IString T) { //1. 创建数组，与模式串字符个数一致 int[] next = new int[T.length()]; int j = 1; // 串的指针 int k = 0; // 模式串的指针（相同字符计数器） // 2 默认情况 next[0] = -1; next[1] = 0; // 3 准备比较 while( j < T.length() -1 ) { // 比较倒数第二个字符 if(T.charAt(j) == T.charAt(k)) { // 连续有字符相等 next[j+1] = k+1; j++; k++; } else if (k == 0) { next[j+1] = 0; j++; } else { //k不是零 k = next[k]; //p119 数学推导 } } // 4 处理完成，返回数组 return next; }
- 处理字符相同
- 处理字符不相等，且k==0
4.8KMP算法：next数组使用
- 主串：ababababaaa
- 模式串：ababaaa
- next数组
/** this 当前串，也就是主串 (this.length() 主串长度) * @param T 模式串 (T.length() 模式串长度) * @param start 从主串中开始位置，例如："abaababaaa".index_KMP("ababaaa",0); */ public int index_KMP(IString T, int start) { //1 准备工作：next数组、指针 int[] next = getNext(T); //1.1 获得模式的next数组 int i = start; //1.2 主串指针 int j = 0; //1.3 模式串的指针 //2 字符比较移动 while(i<this.length() && j<T.length()) { //2.1 串小于长度 if(j == -1 || //2.2.1 第一个字符不匹配，直接跳过 this.charAt(i) == T.charAt(j)) {//2.2.2 字符匹配 i++; j++; } else { j = next[j]; //2.3 移动模式串 } } //3 处理结果 if(j < T.length()) { //3.1 移动位置没有模式串长，不匹配 return -1; } else { return i - T.length(); //3.2 匹配，目前在串后面，需要移动首字符 } }
4.9KMP算法
/** this 当前串，也就是主串 (this.length() 主串长度) * @param T 模式串 (T.length() 模式串长度) * @param start 从主串中开始位置，例如："abaababaaa".index_KMP("ababaaa",0); */ public int index_KMP(IString T, int start) { //1 准备工作：next数组、指针 int[] next = getNext(T); //1.1 获得模式的next数组 int i = start; //1.2 主串指针 int j = 0; //1.3 模式串的指针 //2 字符比较移动 while(i<this.length() && j<T.length()) { //2.1 串小于长度 if(j == -1 || //2.2.1 第一个字符不匹配，直接跳过 this.charAt(i) == T.charAt(j)) {//2.2.2 字符匹配 i++; j++; } else { j = next[j]; //2.3 移动模式串 } } //3 处理结果 if(j < T.length()) { //3.1 移动位置没有模式串长，不匹配 return -1; } else { return i - T.length(); //3.2 匹配，目前在串后面，需要移动首字符 } }
5.数组
5.1概述
数组：一组具有相同数据类型的数据元素的集合。数组元素按某种次序存储在一个地址连续的内存单元空间中。
一维数组：一个顺序存储结构的线性表。[a0,a1,a2, ....]
二维数组：数组元素是一维数组的数组。[ [] , [] , [] ] 。二维数组又称为矩阵。
5.2数组的顺序存储(一维)
多维数组中，存在两种存储方式：
以行序为主序列的存储方式（行优先存储）。大部分程序都是按照行序进行存储的。
以列序为主序列的存储方式（列优先存储）
一维数组内存地址
Loc(0) ：数组的首地址
i ： 第i个元素
L ：每一个数据元素占用字节数
5.3数组的顺序存储(二维)
5.3.1行序
行序：使用内存中一维空间（一片连续的存储空间），以行的方式存放二维数组。先存放第一行，在存放第二行，依次类推存放所有行。
二维数组（n×m）内存地址（以==行序==为主序列）
- Loc(0,0) ：二维数组的首地址
- i ： 第i个元素
- L ： 每一个数据元素占用字节数
- m：矩阵中的列数
注意：
- 如果索引号不是从0开始，不能使用此公式。
- 如果索引号不是从0开始的，需要先将索引号
归零，再使用公式。
5.3.2列序
列序：使用内存中一维空间（一片连续的存储空间），以列的方式存放二维数组。先存放第一列，再存放第二列，依次类推，存放所有列
二维数组（n×m）内存地址（以==列序==为主序列)
5.3.3练习
实例1：
有一个二维数组A[1..6,0..7]，每一个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ ==D== ）个字节。
A. 48
B. 96
C. 252
D. 288
实例2：
设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以==列序==为主顺序存放，则数组元素A[5,8]的存储首地址为（ ）。
A. BA + 141
B. BA + 180
C. BA + 222
D. BA + 225
A[1..8,1..10] --> A[8×10]
- 例如3：
设有数组A[0..8,1..10]，数组的每个元素占5字节，数组从内存首地址BA开始以==列序==为主顺序存放，则数组元素A[7,8]的存储首地址为（ BA + 350 ）。
A[0..8,1..10] --> A[9×10]
5.4特殊矩阵概述
特殊矩阵：具有相同的数据或0元素，且数据分布具有一定规律。
分类：
对称矩阵
三级矩阵
对角矩阵
特殊矩阵只有部分有数据，其他内容为零，使用内存中一维空间（一片连续的存储空间）进行存储时，零元素没有必要进行存储，通常都需要进行压缩存储。
压缩存储：多个值相同的矩阵元素分配同一个存储空间，零元素不分配存储空间。
- 存储有效数据，零元素和无效数据不需要存储。
- 不同的举证，有效和无效定义不同。
5.5对称矩阵压缩存储
5.5.1定义及其压缩方式
什么是对称矩阵：a(i,j) = a(j,i)
对称矩阵的压缩方式：共4种
下三角部分以行序为主序存储的压缩【学习，掌握】
下三角部分以列序为主序存储的压缩
上三角部分以行序为主序存储的压缩
上三角部分以列序为主序存储的压缩
n×n对称矩阵压缩 n (n+1) / 2 个元素，求 1+2+3+...+n的和，只需要计算三角中的数据即可
5.5.2压缩存放及其公式
压缩后存放到一维空间（连续的存放空间中）
对称矩形 A(i,j) 对应 一维数组 s[k] , k与i和j 公式
5.5.3练习
练习1：
a(8,5) -->索引库1,1表示方式
需要将1,1转化成0,0方式，从而可以使用公式，i和j同时-1
a(7,4) -->索引库0,0表示方式
因为：i >= j
k= i(i+1)/2 +j = 7 * 8 / 2 + 4 = 32
32为索引为0的一维数组的下标
数据b下标是从1开始，对应的下标 32+1=33
练习2：
b[13] 下标从1开始，归零
b[12] 下标从0开始，k=12
i*(i+1)/2 , 如果i=4，结果为10
12-10 = j
下标0,0时，a(4,2)
下标1,1时，a(5,3)
5.6三角矩阵
5.6.1概述&存储方式
三角矩阵分为：上三角矩阵、下三角矩阵
上三角矩阵：主对角线（不含主对角线）下方的元素值均为0。只在上三角的位置进行数据存储
下三角矩阵：主对角线（不含主对角线）上方的元素值均为0。只在下三角的位置进行数据存储
存储方式：三角矩阵的存放方式，与对称矩阵的存放方式相同。
5.6.2上三角矩阵
上三角矩阵实例
上三角矩阵对应一维数组存放下标，计算公式 
5.6.3下三角矩阵
下三角矩阵实例`
下三角矩阵对应一维数组存放下标，计算公SH式
5.7对角矩阵
5.7.1定义&名词
对角矩阵：矩阵的所有非零元素都集中在以主对角线为中心的带状区域中，即除主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零。
名词：
半带宽：主对角线一个方向对角线的个数，个数为d。
带宽：所有的对角线的个数。个数为 2d+1
n阶2d+1对角矩阵非零元素个数：n(2d+1) - d(d+1)
n(2d+1) ：下图中所有颜色的个数
d(d+1)/2 ：右下方浅蓝色三角的个数
d(d+1) ：2个三级的个数（右下方、左上方）
一维数组存储个数：n(2d+1) ，若某行没有2d+1个元素，则0补足。
5.7.2压缩存储
压缩后存放一维数组，第一行和最后一行不够2d+1，所以需要补零。
