共计 1749 个字符，预计需要花费 5 分钟才能阅读完成。
模式串 T = ‘abcaabbcabcaabdab’，T 的 next 数组值及 nextval 数组值为（01112231123456712 和 01102131011021701）
a b c a a b b c a b c a a b d a b
maxl
0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1 2
next
0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
nextval
0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
例子：
模式串 a b a a b c a c
next 值 0 1 1 2 2 3 1 2
nextval 值 0 1 0 2 1 3 0 2
1. 第一位的 nextval 值必定为 0，第二位如果于第一位相同则为 0，如果不同则为 1。
2. 第三位的 next 值为 1，那么将第三位和第一位进行比较，均为 a，相同，则，第三位的 nextval 值为 0。
3. 第四位的 next 值为 2，那么将第四位和第二位进行比较，不同，则第四位的 nextval 值为其 next 值，为 2。
4. 第五位的 next 值为 2，那么将第五位和第二位进行比较，相同，第二位的 next 值为 1，则继续将第二位与第一位进行比较，不同，则第五位的 nextval 值为第二位的 next 值，为 1。
5. 第六位的 next 值为 3，那么将第六位和第三位进行比较，不同，则第六位的 nextval 值为其 next 值，为 3。
6. 第七位的 next 值为 1，那么将第七位和第一位进行比较，相同，则第七位的 nextval 值为 0。
7. 第八位的 next 值为 2，那么将第八位和第二位进行比较，不同，则第八位的 nextval 值为其 next 值，为 2。
总而言之，next 和 nextval 数组的前两位一定是 01；
next 数组从第三位开始，取此位前一位 next 数组中的值，找字符串中此值作为序号的字符，与前一位字符进行比较。若相同，为前一位 next 值 +1；若不同，重复上述步骤（这里是再往前取一位），直到序号 1 都不同的话，取 next 值为 1.
nextva 数组从第三位开始，取这一位 next 数组中的值，找字符串中此值作为序号的字符 x，与这一位进行比较。不同，则这一位的 next 值就是其 nextval 值；若相同，重复上述步骤（这里是将 x，与 x 的 next 值对应的序号字符比较），直到序号 1 都相同的话，nextval 值为 0.
两者特征可以简单记为：next 求同最小为 1；nextval 求异最小为 0
char s[6]=”Hello!”是不合法的。
忽略了字符串的大小要比字符串中的字符数多 1 这一点，会造成数组的越界
KMP 算法的特点是在模式匹配时指示主串的指针不会变小。
KMP 匹配时，主串的指针当匹配时会递增，不匹配时会停住不动，也正是因为主串指针没有回滚，KMP 的匹配效率才得以提升
设模式串的长度为 m, 目标串的长度为 n, 当 n≈m 且处理只匹配一次的模式时, 朴素的匹配 (即子串定位函数) 算法所花的时间代价可能会更为节省
朴素的匹配只匹配一次，不用计算 next 数组，所以速度更快
有一个 100*90 的稀疏矩阵, 非 0 元素有 10 个, 设每个整型数占 2 字节, 则用三元组表示该矩阵时, 所需的字节数是(66)
每个非零元素占 3 *2= 6 个字节，共 10 个非零元素，需 6 *10 = 60 个字节；
此外，还一般要用三个整数来存储矩阵的行数、列数和总元素个数，又需要 3 *2 = 6 个字节；
总共：60 + 6 = 66 个字节。
假设以行序为主序存储二维数组 A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为 10，则 LOC(A[5，5])=(818)。
注意基地址是第一个元素的地址，所以要 -1
数组 A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5，5]的地址是(1175)。
与上一个题目的区别：数组从 0 开始算，所以这实际上是一个 6 行 7 列的数组；是列优先而不是习惯的行优先
综上，计算数组中某个元素地址时，要注意数组从 0 还是 1 开始，行优先还是列优先，基地址是第一个元素的地址要减一
理解下数据的结构
首先明确数据具有逻辑结构和存储结构。
逻辑结构指数据元素之间的逻辑关系，有四种关系：集合结构、一对一的线性结构、一对多的树型结构、多对多的图状结构。
存储结构指数据实际存放在计算机中的物理结构，只有两种形式：顺序存储、非顺序存储。
任何一种逻辑结构都可以使用顺序存储或者非顺序存储。
