KMP模式匹配算法探讨(1)
2015-05-30 01:42
导读：计算机应用论文论文，KMP模式匹配算法探讨(1)在线阅读，教你怎么写，格式什么样，科教论文网提供各种参考范例：摘 要 介绍了ＫＭＰ算法并与朴素查找算法进行了比较，提出了前缀函数的概念
摘 要 介绍了ＫＭＰ算法并与朴素查找算法进行了比较，提出了前缀函数的概念，并利用改进的前缀函数改进KMP算法，最后结合ＫＭＰ的改进算法给出了多次匹配的算法。 关键词 串匹配，前缀函数，KMP算法 在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3…sn，模式串表示为T=t1t2…tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。1 KMP算法 最简单的朴素串匹配算法(BF算法)是从主串的第一个字符和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式串的第一个字符进行比较。依次类推，直至模式串和主串中的一个子串相等，此时称为匹配成功，否则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移一个字符，若主串中存在和模式串只有部分匹配的多个子串，匹配指针将多次回溯，而回溯次数越多算法的效率越低，它的时间复杂度一般情况下为O((n-m 1)m) （注：n和m分别为主串和模式串的长度），最坏的情况下为O(m*n)，最好的情况下为O(m n)。KMP模式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中出现失配时，不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符，过滤掉那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配的效率，该算法的时间复杂度为O(m n)。 那么如何确定哪些是多余的比较？ 在KMP算法中通过引入前缀函数f(x)来确定每次匹配不需要比较的字符，保证了匹配始终向前进行，无须回溯。假设主串为s1s2，sn.，模式串为t1t2，tm.，其中 m≦n，从si 1开始的子串遇到一个不完全的匹配，使得：
(1.1) 如果我们能确定一个最小的整数
，使得：
(1.2) 其中
，所以确定i' 等价于确定k，这里的k值就是我们要求的前缀函数f(x)。由式1.1和1.2中K值与主串s无关，只与给定的模式串t中与主串匹配的q有关，即k=f(q)，f(q)=max{i|0 i q且t[1..i]是t[1..q]的后缀} (1.3) 确定KMP前缀函数的算法如下： #define MAXSIZE 100Typedef unsigned char string[MAXSIZE 1];//0号单元用来存放串的长度void f(sstring t, int *array){ m=t[0];//m为当前模式串的长度 array=(int *)malloc((m 1)*sizeof(int));//0号元不用 array[1]=0;k=0; for(q=2;q
