串的模式匹配算法
一、基本概念
1、模式匹配(定位)
设有主串S和子串T(将S称为目标串,将T称为模式串),在主串S中,从位置start开始查找,如若在主串S中找到一个与子串T相等的子串,则返回T的第一个字符在主串中的位置,否则返回-1。
2、算法目的
确定主串中所含子串第一次出现的位置(定位)
3、算法种类
BF算法 (又称古典的、经典的、朴素的、穷举的)
KMP算法
1、Brute-Force算法的设计思想:
• 将主串S的第一个字符和模式T的第1个字符比较,
若相等,继续逐个比较后续字符;
若不等,从主串S的下一字符起,重新与T第一个字符比较。
• 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。
否则,匹配失败,返回值 -1。
2、 Brute-Force算法的实现
typedef struct
{ char str[MaxSize];
int length;
}String;
int BFIndex(String S, int start, String T)
{ int i = start, j = 0, v;
while(i < S.length && j < T.length)
{ if(S.str[i] == T.str[j]) {i++; j++; }
else{ i = i-j+1; j = 0; }
}
if (j==T.length) v=i-T.length;
else v=-1;
return v;
}
3、BF算法的时间复杂度
讨论:
若n为主串长度,m为子串长度,则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m=O(n*m)
最好的情况是:一配就中! 只比较了m次。
最恶劣情况是:主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位比较了m次,别忘了最后m位也各比较了一次,还要加上m!所以总次数为:(n-m)*m+m =(n-m+1)*m
能否利用已部分匹配过的信息而加快模式串的滑动速度?
能!而且主串S的指针i不必回溯!最坏情况也能达到O(n+m)
请看KMP算法!
三、KMP算法
1、KMP算法设计思想:
尽量利用已经部分匹配的结果信息,尽量让i不要回溯,加快模式串的滑动速度。
如图:
需要讨论两个问题:
①如何由当前部分匹配结果确定模式向右滑动的新比较起点k?
② 模式应该向右滑多远才是高效率的?
如图:
新起点 k怎么求?
根据模式串T的规律: “T0…Tk-1”=“Tj-k …Tj-1”
由当前失配位置j(已知) ,可以归纳计算新起点 k的表达式。
如图:
(1)k值仅取决于模式串本身而与相匹配的主串无关。
(2)k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。
(3)这里的两部分子串可以有部分重叠的字符,但不可以全部重叠。
next[j]函数表征着模式T中最大相同前缀子串和后缀子串(真子串)的长度。
可见,模式中相似部分越多,则next[j]函数越大,它既表示模式T字符之间的相关度越高,也表示j位置以前与主串部分匹配的字符数越多。
即:next[j]越大,模式串向右滑动得越远,与主串进行比较的次数越少,时间复杂度就越低(时间效率)。
再想一想:如果主串是外存中一个大文件,用KMP算法效果又如何?
如图:
下一个要讨论的问题是:如何用递推方式来求出最大相同子串的长度呢?这个问题一旦解决,整个KMP算法就可以掌握得很透彻了。
求子串next[i]值的算法:
void GetNext(String T, int next[])
{ int j = 0, k = 0;
next[0] = -1;
while(j < T.length){
if(T.str[j]==T.str[k])
{ next[j+1]=k+1; j++; k++; }
else if (k==0){ next[j+1]=0; j++; }
else k=next[k];
}
}
KMP算法的思想
设s为主串,t为模式串,设i为主串s当前比较字符的下标,j为模式串t当前比较字符的下标,令i和j的初值为0。当si = tj时,i和j分别增1再继续比较;否则 i不变,j改变为next[j]值(即模式串右滑)后再继续比较。依次类推,直到出现下列两种情况之一:一是 j退回到某个j=next[j]值时有si = tj ,则 i和j分别增1后再继续比较;二是j退回到j=-1时,令主串和子串的下标各增1,随后比较si+1和t0 。这样的循环过程一直进行到变量大于等于S.length或变量j大于等于T.length时为止。
KMP算法的实现
第一步,先把模式T所有可能的失配点j 所对应的next[j]计算出来;
第二步:执行定位函数Index_kmp (与BF算法模块非常相似)
int KMPIndex(String S, int start,String T, int next[ ])
{int i=start,j=0,v;
while ( i<=S.length && j<T.length ) {
if (j==-1|| S.str[i] = = T.str[j] ) {i++; j++ } //不失配则继续比较后续字符
else j=next[j]; //特点:S第一步,先把模式T所有可能的失配点j 所对应的next[j]
}
if(j==T.length) v=I-T.length;
else v=-1;
return v;
}
主函数
void main(void)
{ String S = {{"cddcdc"}, 6}, T = {{"cdc"}, 3};
int next[8], pos;
GetNext(T, next);
pos = KMPIndex(S, 0, T, next);
printf("pos = %d\n", pos);
}
2、KMP算法的时间复杂度
回顾BF的最恶劣情况:S与T之间存在大量的部分匹配,比较总次数为: (n-m+1)*m=O(n*m)
而此时KMP的情况是:由于指针i无须回溯,比较次数仅为n,即使加上计算next[j]时所用的比较次数m,比较总次数也仅为n+m=O(n+m),大大快于BF算法
注意:由于BF算法在一般情况下的时间复杂度也近似于O(n+m),所以至今仍被广泛采用。
KMP算法的用途:
因为主串指针i不必回溯,所以从外存输入文件时可以做到边读入边查找——“流水作业”
如图:
- 大小: 26.5 KB
- 大小: 77.9 KB
- 大小: 24.1 KB
- 大小: 78.4 KB
- 大小: 34.6 KB
分享到:
相关推荐
字符串模式匹配算法的改进研究.pdf 字符串模式匹配算法的改进研究.pdf
基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
字符串的模式匹配算法——KMP的C++实现。
C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
大连理工大学数据结构上机题字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
一种改进的串的模式匹配算法的探讨,穆维友,吴泽平,串的模式匹配算法一直都是计算机科学领域的研究焦点之一。本文首先分析了BF、KMP、BM三种算法,并提出了一种改进的Sundaynew算法,给��
该文件讲述了串的模式匹配算法,包括三种算法,使用C#语言。
全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
代码封装了字符串的kmp模式匹配算法。kmp是一种非常快速的字符串匹配算法,效率比普通匹配算法高很多
思想,实现(1)编程动态实现简单模式匹配算法及模式匹配KMP算(2)根据给定的主串与模式串,给出根据两种匹配算法进行匹配的各趟匹配结果; 应用例子: 要求编写建立一个文本文件,每个单词不包括空格且不跨行,...
算法思想:用多模式串建立一个确定性的树形有限状态机,以主串作为该有限状态机的输入,使状态机进行状态的转换,当到达某些特定的状态时,说明发生模式匹配。AC 多模式匹配算法的实现可分预处理和搜索查找两个阶段...
算法思想:用多模式串建立一个确定性的树形有限状态机,以主串作为该有限状态机的输入,使状态机进行状态的转换,当到达某些特定的状态时,说明发生模式匹配。AC 多模式匹配算法的实现可分预处理和搜索查找两个阶段...