下载文档原格式
kmp算法原理
KMP算法（Knuth-Morris-Pratt算法）是一种用于在一个文本串S 中查找模式串P 的有效算法。
它的最大的特点就是当P在S中第一次出现不匹配时，它可以在S中最多只前进一步，而且在前进一步之前，KMP算法可以利用之前匹配过的信息来避免重复匹配。
KMP算法的实现需要预处理模式串P，生成next数组，这个数组用来保存模式串P中每个字符之前的公共前后缀长度。
接着，KMP 算法中的主循环从文本串S的第一个字符开始，并逐个检查S和P 中的字符是否相等。
如果发现不匹配，KMP算法就会按照next数组指定的跳转位置来移动模式串P，而不是每次都从头开始匹配。
KMP算法的运行时间复杂度是O(m+n)，其中m是模式串P的长度，n是文本串S的长度。
KMP算法是一种高效的字符串匹配算法，广泛应用于搜索引擎、编辑器和编译器等软件中。
它的实现简单，运行效率又高，是字符串匹配算法中的经典算法。
实验四：KMP算法实验报告一、问题描述模式匹配两个串。
二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。
注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：int Index(String S,String T,int pos)//参考《数据结构》中的程序{i=pos;j=1;//这里的串的第1个元素下标是1while(i<=S.Length && j<=T.Length){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}//**************(1)}if(j>T.Length) return i-T.Length;//匹配成功else return 0;}匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。
如果T为a bcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。
如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：...ababd...ababc->ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。
kmp算法概念KMP算法概念KMP算法是一种字符串匹配算法，它的全称是Knuth-Morris-Pratt 算法。
该算法通过预处理模式串，使得在匹配过程中避免重复比较已经比较过的字符，从而提高了匹配效率。
一、基本思想KMP算法的基本思想是：当模式串与文本串不匹配时，不需要回溯到文本串中已经比较过的位置重新开始匹配，而是利用已知信息跳过这些位置继续匹配。
这个已知信息就是模式串自身的特点。
二、next数组1.定义next数组是KMP算法中最核心的概念之一。
它表示在模式串中当前字符之前的子串中，有多大长度的相同前缀后缀。
2.求解方法通过观察模式串可以发现，在每个位置上出现了相同前缀和后缀。
例如，在模式串“ABCDABD”中，第一个字符“A”没有任何前缀和后缀；第二个字符“B”的前缀为空，后缀为“A”；第三个字符“C”的前缀为“AB”，后缀为“B”；第四个字符“D”的前缀为“ABC”，后缀为“AB”；第五个字符“A”的前缀为“ABCD”，后缀为“ABC”；第六个字符“B”的前缀为“ABCDA”，后缀为“ABCD”；第七个字符“D”的前缀为“ABCDAB”，后缀为“ABCDA”。
根据上述观察结果，可以得到一个求解next数组的方法：（1）next[0]=-1，next[1]=0。
（2）对于i=2,3,...,m-1，求解next[i]。
①如果p[j]=p[next[j]]，则next[i]=next[j]+1。
②如果p[j]≠p[next[j]]，则令j=next[j]，继续比较p[i]和p[j]。
③重复执行步骤①和步骤②，直到找到满足条件的j或者j=-1。
（3）通过上述方法求解出所有的next值。
三、匹配过程在匹配过程中，文本串从左往右依次与模式串进行比较。
如果当前字符匹配成功，那么继续比较下一个字符；否则利用已知信息跳过一些位置继续进行匹配。
具体地：（1）如果当前字符匹配成功，则i和j都加1。
（2）如果当前字符匹配失败，则令j=next[j]。
KMP算法（改进的模式匹配算法）——next函数KMP算法简介KMP算法是在基础的模式匹配算法的基础上进⾏改进得到的算法，改进之处在于：每当匹配过程中出现相⽐较的字符不相等时，不需要回退主串的字符位置指针，⽽是利⽤已经得到的部分匹配结果将模式串向右“滑动”尽可能远的距离，再继续进⾏⽐较。
在KMP算法中，依据模式串的next函数值实现字串的滑动，本随笔介绍next函数值如何求解。
next[ j ]求解将 j-1 对应的串与next[ j-1 ]对应的串进⾏⽐较，若相等，则next[ j ]=next[ j-1 ]+1;若不相等，则将 j-1 对应的串与next[ next[ j-1 ]]对应的串进⾏⽐较，⼀直重复直到相等，若都不相等则为其他情况题1在字符串的KMP模式匹配算法中，需先求解模式串的函数值，期定义如下式所⽰，j表⽰模式串中字符的序号（从1开始）。
若模式串p 为“abaac”，则其next函数值为（）。
解：j=1，由式⼦得出next[1]=0；j=2，由式⼦可知1<k<2，不存在k，所以为其他情况即next[2]=1；j=3，j-1=2 对应的串为b，next[2]=1，对应的串为a，b≠a，那么将与next[next[2]]=0对应的串进⾏⽐较，0没有对应的串，所以为其他情况，也即next[3]=1；j=4，j-1=3 对应的串为a，next[3]=1，对应的串为a，a=a，所以next[4]=next[3]+1=2；j=5，j-1=4 对应的串为a，next[4]=2，对应的串为b，a≠b，那么将与next[next[4]]=1对应的串进⾏⽐较，1对应的串为a，a=a，所以next[5]=next[2]+1=2；综上，next函数值为 01122。
题2在字符串的KMP模式匹配算法中，需先求解模式串的函数值，期定义如下式所⽰，j表⽰模式串中字符的序号（从1开始）。
若模式串p为“tttfttt”，则其next函数值为（）。
KMP算法改进版本介绍1. 引言KMP算法是一种高效的字符串匹配算法，它在处理文本串与模式串匹配的过程中，通过利用已经得到的匹配信息，避免重复比较已经匹配过的字符。
然而，原始的KMP算法在某些情况下可能会存在性能上的瓶颈，因此改进版本的KMP算法被提出。
本文将介绍改进版本的KMP算法及其相关优化措施。
2. 改进版本的KMP算法原理改进版本的KMP算法在原有的算法基础上进行改进，主要的改进点包括：（1）失配时如何选择跳转的位置；（2）在生成模式串的最大匹配前缀和最大匹配后缀的过程中，如何避免重复计算。
3. 失配时的跳转策略在传统的KMP算法中，当发生失配时，模式串向右移动一位作为下一次比较的起始位置。
而在改进版本的KMP算法中，可以根据已经得到的匹配信息，选择一个更优的跳转位置。
具体策略如下：（1）当某个字符失配时，记录失配位置的前一个字符在模式串中的最右出现位置，记为rightmost。
（2）如果在模式串的rightmost右侧存在与当前失配字符相等的字符，则跳转到该字符所在的位置，这样可以在某种程度上避免不必要的比较。
4. 避免重复计算在生成模式串的最大匹配前缀和最大匹配后缀时，传统的KMP算法要重新比较模式串的前缀和后缀是否匹配。
而在改进版本的KMP算法中，可以利用已经得到的匹配信息，避免重复计算。
具体方法如下：（1）定义一个辅助数组nextval[]，用于保存每个字符对应的最长匹配前缀的下一个字符位置。
（2）在生成nextval[]的过程中，如果当前字符失配，将跳转到其对应的nextval[]值所对应的位置。
这样可以直接跳过已经匹配的前缀，避免重复比较。
5. 改进版本的KMP算法实现改进版本的KMP算法的实现与原始版本类似，只是在失配时的跳转策略以及避免重复计算的方法上有所差异。
具体实现步骤如下：（1）初始化文本串和模式串的指针i和j，表示当前比较的位置。
（2）如果当前字符匹配，则i和j分别向后移动一位。
KMP算法的时间复杂度KMP算法是一种字符串匹配算法，它可以在一个主串中高效地查找所有匹配某个模式串的位置。
在计算机科学中，算法的时间复杂度是衡量算法执行时间与输入规模之间关系的度量。
在本文中，我们将深入探讨KMP算法的时间复杂度。
KMP算法的时间复杂度可通过三个方面来分析：预处理阶段的时间复杂度、匹配阶段的时间复杂度以及总体时间复杂度。
1. 预处理阶段的时间复杂度在KMP算法中，要先对模式串进行预处理，生成部分匹配表（Partial Match Table），也称为最长公共前后缀表（Longest Proper Prefix which is also Sufix，简称为LPS表）。
这个过程的时间复杂度是O(m)，其中m是模式串的长度。
在生成部分匹配表的过程中，KMP算法利用了前缀与后缀的性质，通过动态规划的方式计算每个位置的最长匹配长度。
虽然这个过程需要遍历整个模式串，但是每次计算的操作都具有重叠子问题的性质，因此可以通过状态转移方程高效地计算出来。
2. 匹配阶段的时间复杂度在匹配阶段，KMP算法将主串与模式串进行逐个字符的比较，并利用已经生成的部分匹配表来决定下一次比较的位置。
这个过程的时间复杂度是O(n)，其中n是主串的长度。
在匹配过程中，KMP算法利用了部分匹配表的信息，根据当前位置的匹配长度来确定下一次比较的位置。
通过避免无效的比较，KMP 算法可以在最坏情况下实现线性的时间复杂度。
3. 总体时间复杂度KMP算法的总体时间复杂度是预处理阶段的时间复杂度与匹配阶段的时间复杂度之和。
即O(m) + O(n) = O(m + n)。
从总体时间复杂度可以看出，KMP算法的执行时间与主串和模式串的长度之和成正比。
相比于朴素的字符串匹配算法，KMP算法可以大大提高匹配的效率，尤其是在模式串较长的情况下。
总结：KMP算法的时间复杂度是O(m + n)，其中m是模式串的长度，n是主串的长度。
通过对模式串进行预处理并利用部分匹配表的信息，KMP算法可以高效地在主串中查找所有匹配模式串的位置。
KMP模式匹配算法KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。
该算法的核心思想是通过预处理模式串，构建一个部分匹配表，从而在匹配过程中尽量减少不必要的比较。
KMP算法的实现步骤如下：1.构建部分匹配表部分匹配表是一个数组，记录了模式串中每个位置的最长相等前后缀长度。
从模式串的第二个字符开始，依次计算每个位置的最长相等前后缀长度。
具体算法如下：-初始化部分匹配表的第一个位置为0，第二个位置为1- 从第三个位置开始，假设当前位置为i，则先找到i - 1位置的最长相等前后缀长度记为len，然后比较模式串中i位置的字符和模式串中len位置的字符是否相等。
- 如果相等，则i位置的最长相等前后缀长度为len + 1- 如果不相等，则继续判断len的最长相等前后缀长度，直到len为0或者找到相等的字符为止。
2.开始匹配在主串中从前往后依次查找模式串的出现位置。
设置两个指针i和j，分别指向主串和模式串的当前位置。
具体算法如下：-当主串和模式串的当前字符相等时，继续比较下一个字符，即i和j分别向后移动一个位置。
-当主串和模式串的当前字符不相等时，根据部分匹配表确定模式串指针j的下一个位置，即找到模式串中与主串当前字符相等的位置。
如果找到了相等的位置，则将j移动到相等位置的下一个位置，即j=部分匹配表[j]；如果没有找到相等的位置，则将i移动到下一个位置，即i=i+13.检查匹配结果如果模式串指针j移动到了模式串的末尾，则说明匹配成功，返回主串中模式串的起始位置；如果主串指针i移动到了主串的末尾，则说明匹配失败，没有找到模式串。
KMP算法的时间复杂度为O(m+n)，其中m为主串的长度，n为模式串的长度。
通过预处理模式串，KMP算法避免了在匹配过程中重复比较已经匹配过的字符，提高了匹配的效率。
总结：KMP算法通过构建部分匹配表，实现了在字符串匹配过程中快速定位模式串的位置，减少了不必要的比较操作。
数据结构—串的模式匹配数据结构—串的模式匹配1.介绍串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。
本文档将详细介绍串的模式匹配算法及其实现。
2.算法一：暴力匹配法暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。
具体步骤如下：1.从主串的第一个字符开始，逐个比较主串和模式串的字符。
2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。
3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。
3.算法二：KMP匹配算法KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。
具体步骤如下：1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。
2.从主串的第一个字符开始，逐个比较主串和模式串的字符。
3.如果当前字符匹配成功，则继续比较下一个字符。
4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。
4.算法三：Boyer-Moore匹配算法Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。
具体步骤如下：1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。
2.从主串的第一个字符开始，逐个比较主串和模式串的字符。
3.如果当前字符匹配成功，则继续比较下一个字符。
4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。
5.算法四：Rabin-Karp匹配算法Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。
具体步骤如下：1.计算模式串的哈希值。
2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。
KMP算法-易懂版⼀：定义 Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常⽤于快速查找⼀个母串S中是否包含⼦串(模式串)P，以及P出现的位置。
由于简单的暴⼒匹配中，每次遇到不匹配的位置时都要回溯到母串上⼀次的起点 i +1的位置上再次从⼦串的开头进⾏匹配，效率极其低下，故⽽KMP算法应运⽽⽣，减少回溯过程中不必要的匹配部分，加快查找速度。
⼆：kmp算法求解步骤描述 若当前不匹配的位置发⽣在母串位置 i，⼦串位置 j 上，则：1. 寻找⼦串位置 j 之前元素的最长且相等的前后缀，即最长公共前后缀。
记录这个长度。
2. 根据这个长度求 next 数组3. 若 j != 0, 则根据next [j] 中的值，将⼦串向右移动，也就是将公共前缀移到公共后缀的位置上，(代码表⽰为：j=next [j]，注意 i 不变)，即对位置 j 进⾏了更新，后续⼦串直接从更新后的 j 位置和母串 i 位置进⾏⽐较。
4. 若 j == 0，则 i+1，⼦串从j位置开始和母串 i+1 位置开始⽐较。
综上，KMP的next 数组相当于告诉我们：当⼦串中的某个字符跟母串中的某个字符匹配失败时，⼦串下⼀步应该跳到哪个位置开始和母串当前失配位置进⾏⽐较。
所以kmp算法可以简单解释为：如⼦串在j 处的字符跟母串在i 处的字符失配时，下⼀步就⽤⼦串next [j] 处的字符继续跟⽂本串 i 处的字符匹配，相当于⼦串⼀次向右移动 j - next[j] 位，跳过了⼤量不必要的匹配位置(OK，简单理解完毕之后，下⾯就是求解KMP的关键步骤，Let’s go! ) 三：kmp算法关键步骤之⼀，求最长的公共前后缀！ 箭头表⽰当前匹配失败的位置，也就是当前的 j 位置。
⽩框表⽰最长公共前后缀AB！此时长度为2！ 再来⼀个，此时最长公共前后缀为ABA！长度为3！四：kmp算法关键步骤之⼆，求next[ ] 数组 由步骤⼀，我们可以得到⼦串每个位置前⾯元素的最长共同前后缀，注意⼦串第⼀个位置是没有前后缀的，所以长度为0！ 例：⼦串ABCDABD的最长公共前后缀可表⽰如下。
模式匹配的KMP算法学生姓名：侯成龙指导老师：罗心摘要本课程设计主要解决用模式匹配的KMP算法进行字串定位的程序设计。
在本课程设计中，系统开发平台为Windows XP，程序设计设计语言采用Visual C++6.0，程序运行平台为Windows 98/2000/XP。
在程序设计中，采用了串的KMP模式匹配算法实现了子串的定位操作。
程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以解决实际问题。
关键词程序设计；串的模式匹配；KMP算法；Visual C++6.01 引言子串定位运算通常称为串的模式匹配或串匹配运算，是串处理中最重要的运算之一，应用非常广泛[1]。
本课程设计主要解决用模式匹配的KMP算法进行字串定位的程序设计。
1.1 课题背景计算机上的非数值处理的对象基本上是字符串数据。
在较早的程序设计语言中，字符串是作为输入和输出的常量出现的。
随着语言加工程序的发展，产生了字符串处理。
这样，字符串也就作为一种变量类型出现在越来越多的程序设计语言中，同时也产生了一系列字符串的操作。
字符串一般简称为串。
在汇编和语言的编译程序中，源程序及目标程序都是字符串数据。
在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的。
又如信息检索系统、文字编辑程序、问答系统、自然语言翻译系统以及音乐分析程序等，都是以字符串数据作为处理对象的[2]。
数据结构是指相互之间存在一定关系的数据元素的集合。
按照视点的不同，数据结构分为逻辑结构和存储结构。
数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的整体。
所谓逻辑关系是指数据元素之间的关联方式或邻接关系。
根据数据元素之间逻辑关系的不同，数据结构分为四类：集合；线性结构；树结构；图结构。
数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。
为了区别于数据的存储结构，常常将数据的逻辑结构称为数据结构。
数据的存储结构(storage structure)又称为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素之外，必须隐式或显示地存储数据元素之间的逻辑关系。
通常有两种存储结构：顺序存储结构和链接存储结构[3]。
串(string)（或字符串）是由零个或多个字符组成的有限序列，一般记为s ='a1a2…an'(n>=0)。
其中，s是串的名，用单引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n称为串的长度。
零个字符的串称为空串，他的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。
包含子串的串相应的称为主串。
通常称字符在序列中的序号为该字符串在串中的位置。
子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。
在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可以用定长数组来描述之。
子串定位运算通常称为串的模式匹配或串匹配运算，是串处理中最重要的运算之一，应用非常广泛。
例如，在文本编辑程序中，我们经常要查找某个特定单词在文本中出现的位置。
显然解决该问题的有效算法能极大地提高文本编辑程序的响应性能[4]。
在计算机科学领域，串的模式匹配算法一直都是研究焦点之一。
串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，ＫＭＰ算法是字符串查找算法中的一个经典算法，该算法在最坏情况下具有线性的查找时间，查找效率高[5]。
1.2 课程设计目的子串定位就是要在主串s中找到一个与子串t相同的子串。
通常我们把主串s称为目标串，把子串t称为模式串，把从目标串s中查找t子串的定位过程称为串的“模式匹配”。
模式匹配有两种结果：若从主串s中找到模式为t的子串，则返回t子串在s中的起始位置。
当s中有多个模式匹配为t的子串时，通常只找出第一个子串的起始位置，这种情况称为匹配成功，否则称为匹配失败[6]。
本课程设计主要是用模式匹配的KMP算法实现子串的定位操作，通过程序的编写、调试和运行可以进一步掌握数据结构及算法的程序实现的基本方法。
理解子串定位操作的实现过程以及KMP算法对基本模式匹配算法的改进之处。
1.3课程设计内容本课程设计主要完成改进基本的模式匹配算法，运用KMP算法实现串的模式匹配的程序设计。
例如，运行改进后程序时，输入主串s=“addabbcgsa”，模式串ｔ＝“abbc”时，显示模式匹配成功，模式串在主串的位置从第4个字符开始；如果输入输入主串s=“addabbcgsa”，模式串ｔ＝“absc”时，则显示模式匹配不成功，在主串中未找到模式串。
2 设计思路与方案2.1设计思路注意到模式匹配的KMP算法是对模式匹配简单算法改进后的算法，所以有必要先介绍简单模式匹配算法及其基本思想，进而提出一种改进后的模式匹配算法---KMP算法。
因为KMP算法是在已知模式串的next函数值的基础上执行的，所以又要先实现求模式串next 函数值的算法。
2.2设计方案在本课程设计中，运用串的模式匹配的KMP算法进行子串的定位操作，要实现这一过程主要用到以下函数：求next函数值的算法：void GetNext(char T[MAXSTRLEN],int (&next)[64])计算next函数修正值的算法：void GetNextVal(char T[MAXSTRLEN],int (&next)[64])KMP算法：int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64],int pos) 主函数：void main()3 详细实现3.1模式匹配的基本算法采用定长顺序存储结构，可以写出不依赖于其他串操作的基本匹配算法。
该算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。
依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为零。
算法如下：int Index(SString S,SString T,int pos) {//返回子串T在主串S中的第pos个字符之后的位置的。
若不存在，则函数值为0。
//其中，T非空，１≤pos≤StrLength(S)。
int i=pos; int j=1;while (i<=S[0]&&j<=T[0]) {if (S[i]==T[j]) {++i;++j;}else {i=i-j+2; j=1;}}if(j>T[0]) return i-T[0];else return 0;}// Index3.2模式匹配的改进算法——KMP算法这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP 算法。
此算法可以在O(n+m)的时间内数量级上完成串的模式匹配操作。
其改进之处在于：每当一趟匹配过程中出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
KMP算法如下：int Index_KMP(SString S,SString T,int (&nextval)[64],int pos) {//利用模式串T的next函数T求T在主串S中的第pos个字符之后的位置的// ＫＭＰ算法。
其中，T非空，１≤pos≤StrLength(S)。
int i=pos; int j=1;while (i<=S[0]&&j<=T[0]) {if (j==0||S[i]==T[j]) {++i;++j;}else j=nextval[j];}if(j>T[0]) return i-T[0];else return 0;}// Index_KMP模式串的next函数的定义：例如： P="abaabcac"则[7]3.3模式串next函数值的算法及next修改值的算法KMP算法是在已知模式串的next函数值的基础上执行的，求next函数值的算法如下所示：void get_next(SString T, int next [ ]) {//求模式串T的next函数值并存入数组next。
i=1; next [1]=0; j=0;while(i<T[0]) {if (j==0||T[i]==T[j]) {++i; ++j;next [i]=j;}else j=next[j];}}//get_next以上定义的next函数在某些情况下尚有缺陷。
进行修正，可得计算next函数修正值的算法如下（此时匹配算法不变）：void get_nextval(SString T, int (&nextval)[64]) {//求模式串T的next函数修正值并存入数组nextval。
int i=1; nextval[1]=0; int j=0;while(i<T[0]) {if (j==0||T[i]==T[j]) {++i; ++j;if (T[i]!=T[j]) nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];}}//get_nextval3.4程序运行过程将以上主要函数加以主函数写出完整的C语言代码，在Visual C++6.0中运行。
本操作的流程图如下所示：图3-14 运行环境与结果4.1运行环境在本课程设计中，系统开发平台为Windows2000,程序设计语言为Visual C++6.0，程序的运行环境为Visual C++ 6.0。
Visual C++一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。
实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C++ 6.0为编程环境。
Microsoft Visual C++ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C++程序开发包。
Visual C++包中除包括C++编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。
自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。
