这章就更水了，前半章是我心中的复习快乐章，kmp有点死亡。
1 数组寻址定义a[9][8][7]，a[1][2][3]是数组中第几个元素
这个从python的角度更好理解一些，三维数组的python输出结果是（可能不标准）
[ [ 0 1 2 3 4 5 6 7 8 9 0 1] [ 0 1 2 3 4 5 6 7 8 9 0 1] [ 0 1 2 3 4 5 6 7 8 9 0 1] ]
就是说，三维只不过是把多个二维堆起来，所以
&a[1][2][3] = &a[0][0][0] + sizeof(type) * 1 * 8 * 7 + 2 * 7 + 3
对角矩阵：就存主对角线上的一维数组即可。
三角矩阵：把上三角/下三角按行撕成一维数组即可。
对称矩阵：当成上三角存。
2.2 稀疏矩阵与三元组表是指当一个矩阵非常大，但是只有个别的元素是非0元素，就可以只存非0元素即可，也分数组和链表两种方式。
三元组表：每一个里存该非0元素的，行、列、值。按行优先存储。
对于转置矩阵来说，三元组表非常有效，但是如果需要对某一列进行全部元素的操作（例：对第二列的所有元素+5），用三元组表需要遍历整个表格，则需要用十字链表。
十字链表：每个行和列有一个行的头和列的头，然后每一行、每一列都分别是一个循环链表，如书上P52图，这样对一行/一列操作就通过表头遍历循环链表即可。
2.3 字符串kmp前的都自己看吧，很简单。
重点：不要去网上随便扒kmp的教程，因为不同的教程失败函数的结果可能不一样，如果期末考填空题，用其他教程得到的结果可能会错误。多看看书上这种吧，书上这种失败函数是最不好理解的失败函数方式。下面相应的算法也是随着失败函数的定义方式改变的。
2.3.1 失败函数void fail(string s) {
int len=s.length();
int i=0;
Next[0]=-1;
//假设当前的字母为m，上一个字母为n
for(int j=1;j=0) i=Next[i]; //不断Next找上一个n的后一个是不是m
//下面这个if&else是经典的，判断上一个while循环是通过何种方式结束
if(s[j]==s[i+1]) Next[j]=i+1; //如果是，那就对上了
else Next[j]=-1; //一直都对不上，那就是新的
}
}
这个肯定还是不能让你完全明白，那么我现在要举栗子了
(是一个字符串，空格是方便观看)
-
abcf abcf abcf 的失败函数是：
-1 -1 -1 -1 0 1 2 3 4 5 6 7
这个不用特意去通过代码理解，主要是明白失败函数的简单运行方式，但是这样往往会导致错误的理解：就是从头开始比较连续的第几个和当前元素一样且数字连续。 -
abcf abcd abcf 的失败函数是
-1 -1 -1 -1 0 1 2 -1 0 1 2 3
我们可以从这里看到，当字符匹配不上的时候就为-1，但是这里数字也是连续的，即从-1开始的每次+1的递增序列。 -
abcf abcd abcf abcf 当判断最后一个f时，此时前面的失败函数是这样：
-1 -1 -1 -1 0 1 2 -1 0 1 2 3 4 5 6
当我们开始读取最后一个字符’f’时，如何判断它的失败函数呢？为了方便观看，我把代码贴到下面。这里我们发现最后一个数字是3，跟前面就不是连续的了，看起来的规律不一定准确，千万要用代码实现一遍。
i=Next[j-1];
// i=Next[14] = 6 首先找f字母的上一个字母c，c的Next是6
while(s[j]!=s[i+1]&&i>=0) i=Next[i];
// s[15]=f ≠ s[7]=d i=Next[6] = 2
// s[15]=f =s[3]=f 跳出循环
//值得注意的是，如果最开始加一句i=j-1=14，将第一句改成第一次i=Next[i]
//在这里最开始i曾被赋值为14，6，2，且这三个位置上的字母都是c
//且Next[14]=6，Next[6]=2，就是分别用7和3与15比较是否相同
if(s[j]==s[i+1]) Next[j]=i+1;
//因为是通过s[j]==s[i+1]跳出while，所以走这条if，Next[15]=3
2.3.2 KMP算法
int kmp(string s, string p){ // s是父串，p是子串
int len_s = s.length();
int len_p = p.length();
int i = 0, j = 0; // i是父串的指针，j是子串的指针
while (i < len_s && j < len_p){
if (s[i] == p[j]){ // 当前位置匹配成功
i++; j++; // 指针都向后移动一位
if(j==len_p) return i-len_p; //匹配结束，返回匹配位置
}
else{
//子串第一位都匹配失败，找父串下一个字母匹配
if(j==0) i++;
//字串非第一位匹配失败，那找该字母的上一位的Next的下一位
else j=Next[j-1]+1;
}
}
return -1;
}
对于 abcf abcd abcf abcf 这个字符串，失败函数为
-1 -1 -1 -1 0 1 2 -1 0 1 2 3 4 5 6 3
当前14位都匹配成功，到第15位f匹配失败的时候，那就找第14位的Next，j=Next[14]=6；查询第7位字母为d≠f，会继续匹配失败找j=Next[6]=2；查询第3位字母为f匹配成功，走向i++&j++。
上述过程一共进行三次循环：第一次匹配失败j=Next[14]=6，第二次匹配失败j=Next[6]=2，第三次匹配成功i++&j++。
2.3.3 补充对于书上这种kmp，我能说的言尽于此，我当时理解的过程也都在这里，如果还是觉得不懂，就多找数据一遍遍手动过代码，就能理解好了。
