大连海事大学计算机考研——KMP排序

2022-09-23 05:36:39 考研全封闭培训 5

[摘要]

??题型判断（20*1）+ 选择（10*2）+简答（含树和森林的转化，时间复杂度，二叉排序树，平衡二叉树，KMP，Hash表，程序输出等）+证明（15*1） + 编程（15*1） KMP排序这种类型的题不难，掌握了方法就没问题，主要是注意细心，以及要有足够的熟练...

??题型判断（20*1）+ 选择（10*2）+简答（含树和森林的转化，时间复杂度，二叉排序树，平衡二叉树，KMP，Hash表，程序输出等

）+证明（15*1） + 编程（15*1）

KMP排序

这种类型的题不难，掌握了方法就没问题，主要是注意细心，以及要有足够的熟练度。例题

编号 j 写成 1 2 3 4Next【j】前两个，无论什么字段，都记为0，1

第三个，aaa，前两位aa，重复字段a，（即前N-1位的重复字段长度+1），2

第四个，aaad，前三位aaa，重复的字段aa（不可将aaa视为和自身重合），3

第五个，aaade，前四位aaad，重复的字段空，0+1 = 1

第六个，aaadea，前五位aaade，重复的字段空，0+1 = 1

第七个，aaadeaa，前六位aaadea，重复的字段 a，2

第八个，aaadeaaa，前七位aaadeaa，重复的字段 aa，3

第九个，aaadeaaaad，前八位aaadeaaa，重复的字段 aaa，4

往下就不一一写了，方法就是这样。重复字段：从前往后与从后往前的字段相同。

3.NextVal【j】

核心：相同就写别人的NextVal，不同就写自己的Next。

1.第一位，都写0

2.第二位，Next【j】 = 1，T【1】 = a= T【2】，相同，

写T【1】对应的NextVal【j】，即NextVal【1】 = 0

3.第三位，Next【j】 = 2，T【2】= T【1】 =a= T【3】，相同，

写T【1】对应的NextVal【j】，即NextVal【1】 = 0

注：这里一定要回溯到首位，即T1

4.第四位，Next【j】 = 3，T【3】 = a ≠ d = T【4】，不同，

写T【4】对应的Next【j】，即NextVal【4】

= 3

5.第五位，Next【j】 = 1，T【1】 = a ≠ e = T【5】，不同，

写T【5】对应的Next【j】，即NextVal【5】 = 1

下同，写一下第九个

6.第九位，Next【j】 = 4，T【4】 = d = T【9】，相同，

写T【4】对应的NextVal【j】，即NextVal【4】 = 3

4.匹配过程

1.比较失败后，失败数值对应的NextVal为几，就表示下次比较从第几位开始。

2.前面的未比较的也写上，建议用括号括起来，这些是不用比较的。

3.每一行未在括号里面的，就是比较的次数。

4.有几行就是比较了几次，建议写在每行后面，用 j = 123来表示。

结语：KMP属于必考题，但每年的题型固定，难度较小。

有一年考的是从第n位开始匹配，不是第一位，这是可能出现的坑。

做这种题，一是，保持熟练度；二是，认真仔细。