|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 线性结构 > 串 >
|
|
相关知识点：4个
|
|
|
|
|
子串（也称为模式串）在主串中的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。
|
|
|
|
|
|
该算法也称为布鲁特一福斯算法，其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续下一对字符的比较，否则从主串的第二个字符起与模式串的第一个字符重新开始比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。
|
|
|
|
【函数】以字符数组存储字符串，实现朴素的模式匹配算法。
|
|
|
|
|
|
假设主串的长度为n，模式串的长度为m，下面分析朴素模式匹配算法的时间复杂度，位置序号从1开始计算。设从主串的第i个位置开始与模式串匹配成功，而在前i-1趟匹配中，每趟不成功的匹配都是模式串的第一个字符与主串中相应的字符不相同，则在前i-1趟匹配中，字符的比较共进行了i-1次，因第i趟成功匹配的字符比较次数为m，所以总的字符比较次数为（i-1+m）且1≤i≤n-m+1。若在这n-m+1个起始位置上匹配成功的概率相同，则在最好情况下，匹配成功时字符间的平均比较次数为：
|
|
|
|
|
|
因此，在最好情况下匹配算法的时间复杂度为O（n+m）。而在最坏的情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等。若第i趟匹配时成功，则前i-1趟不成功的匹配加上最后一趟成功的匹配，每趟的字符比较次数都是m次，总共比较了i×m次。因此，最坏情况下的平均比较次数为：
|
|
|
|
|
|
由于n?m，所以该算法在最坏情况下的时间复杂度为O（n×m）。
|
|
|
|
|
|
改进的模式匹配算法又称为KMP算法（由D.E.Knuth、V.R.Pratt和J.H.Morris提出），其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串字符的位置指针，而是利用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。此算法可在O（n+m）的时间内完成。
|
|
|
