 实现功能： 从主串中第K个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。要求用三种模式匹配算法分别实现：  朴素的模式匹配算法（BF算法） KMP改进算法(Next[ ]) KMP改进算法(NextVal[ ]) 设计要求： 首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 程序运行后，给出5个菜单项的内容和输入提示： 1．输入主串、子串和匹配起始位置 2．朴素的模式匹配算法 3．KMP改进算法(Next[ ]) 4．KMP改进算法(NextVal[ ]) 0．退出管理系统 请选择0—4： 菜单设计要求：使用数字0—4来选择菜单项，其它输入则不起作用。 输出结果要求：输出各趟匹配详细过程（其中3、4，首先输出Next[ ]或者NextVal[ ]的各元素的数值），然后输出匹配总趟数、单个字符比较次数、匹配成功时的位置序号或者匹配失败提示信息。

模式匹配算法概述

模式匹配算法是计算机科学中用于在文本中查找特定模式或子串的算法。在本问题中，我们关注三种模式匹配算法：朴素的模式匹配算法（BF算法）、KMP改进算法以及KMP改进算法的变种NextVal[]。

朴素的模式匹配算法（BF算法）

朴素的模式匹配算法是一种简单的字符串搜索方法。它通过在主串中逐个位置尝试匹配子串，如果当前位置不匹配，则将子串向右移动一位继续尝试匹配。这种方法在最坏情况下的时间复杂度为O(n*m)，其中n是主串长度，m是子串长度510。

KMP改进算法（Next[]）

KMP算法通过预处理模式串来创建一个名为"next"的数组，该数组用于在不匹配的情况下跳过尽可能多的字符。"next"数组的每个元素表示在当前位置不匹配时，模式串应该回退到哪个位置重新开始匹配67。这种方法的时间复杂度为O(n+m)。

KMP改进算法（NextVal[]）

NextVal[]是KMP算法的一个变种，它在next数组的基础上增加了额外的信息，用于在不匹配时更精确地确定模式串的回退位置4。

设计要求

主控菜单程序设计

设计一个主控菜单程序，包含以下五个菜单项：

1. 输入主串、子串和匹配起始位置
2. 朴素的模式匹配算法
3. KMP改进算法(Next[])
4. KMP改进算法(NextVal[])
5. 退出管理系统

菜单设计

使用数字0-4来选择菜单项，其他输入无效。

输出结果要求

• 对于每个算法，首先输出匹配详细过程。
• 对于KMP算法的变种（3和4），首先输出next数组或NextVal数组的元素值。
• 输出匹配总趟数、单个字符比较次数。
• 如果匹配成功，输出匹配成功时的位置序号；如果匹配失败，给出相应的提示信息。

实现步骤

1. 输入阶段：用户输入主串、子串和匹配起始位置。
2. 算法选择：用户通过选择菜单项来指定使用哪种模式匹配算法。
3. 算法执行：
   • 对于BF算法，逐个位置尝试匹配子串。
   • 对于KMP算法，使用next数组进行匹配。
   • 对于NextVal算法，使用NextVal数组进行匹配。
4. 结果输出：根据算法执行结果，输出匹配过程、总趟数、字符比较次数和匹配结果。

结论

通过实现这三种模式匹配算法，用户可以更有效地在主串中查找子串的位置。每种算法都有其特点和适用场景，用户可以根据具体需求选择合适的算法进行模式匹配。