文档介绍：1第4章串(String):确定主串中所含子串第一次出现的位置(定位)(又称古典的、经典的、朴素的、穷举的)KMP算法算法种类:带回溯,速度慢避免回溯,匹配速度快,是全课程的亮点之一定位问题称为串的模式匹配,典型函数为Index(S,T,pos)3BF算法的实现—即编写Index(S,T,pos)函数例1:S=‘ababcabcacbab’,T=‘abcac’,pos=1, 求:串T在串S中第pos个字符之后的位置。利用演示系统看BF算法执行过程。BF算法设计思想:将主串S的第pos个字符和模式T的第1个字符比较,若相等,继续逐个比较后续字符;若不等,从主串S的下一字符(pos+1)起,重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。否则,匹配失败,:若n为主串长度,m为子串长度,则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m=O(n*m)一般的情况是:O(n+m)推导方法:要从最好到最坏情况统计总的比较次数,然后取平均。BF算法的时间复杂度最好的情况是:一配就中!只比较了m次。能否加快子串(又称模式串)的滑动速度?能!利用已部分匹配过的信息使主串S的指针i不必回溯,最坏情况也能达到O(n+m)请看KMP算法!最坏的情况是:主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位比较了m次,别忘了最后m位也各比较了一次,还要加上m!所以总次数为:(n-m)*m+m=(n-m+1)*m5KMP算法(特点:速度快)①KMP算法设计思想②KMP算法的推导过程③KMP算法的实现(关键技术:计算next[j])④KMP算法的时间复杂度全书一大亮点!6尽量利用已经部分匹配的结果信息,尽量让i不要回溯,加快模式串的滑动速度。例:①KMP算法设计思想:(参见教材P80-84)S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’Index_kmp的返回值应为i=6需要讨论两个问题:①如何由当前部分匹配结果确定模式向右滑动的新比较起点k?②模式应该向右滑多远才是高效率的?iiikkabaabckiii-T[0]7奇妙的结果:k仅与模式串T有关!②KMP算法的推导过程:(见教材P81)请抓住部分匹配时的两个特征:两式联立可得:‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’S=‘ababcabcacbab’T=‘abcac’ik则T的k-1~1位=S前i-1~i-(k-1)位即(4-2)式含义设目前打算与T的第k字符开始比较(1)(2)‘T1…Tk-1’则T的j-1~j-(k-1)位=S前i-1~i-(k-1)位即(4-3)式含义ikjS=‘ababcabcacbab’T=‘abcac’刚才肯定是在S的i处和T的第j字符处失配‘Tj-(k-1)…Tj-1’截取一段,但k有限制,1<k<jk是追求的新起点加速的前提:T首与Tj处有相同子串注意:j为当前已知的失配位置,我们的目标是计算新起点k。式中仅剩一个未知数k,理论上已可解!8根据模式串T的规律:‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’由当前失配位置j(已知),可以归纳出计算新起点k的表达式。next[j]=0当j=1时//不比较max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况讨论:(1)next[j]的物理意义是什么?(2)next[j]具体怎么求?—即KMP算法的实现令k=next[j](k与j显然具有函数关系),则取T首与Tj处最大的相同子串新起点k怎么求?9(1)next[j]有何物理意义?next[j]函数表征着模式T中最大相同前缀子串和后缀子串(真子串)的长度。可见,模式中相似部分越多,则next[j]函数越大,它既表示模式T字符之间的相关度越高,也表示j位置以前与主串部分匹配的字符数越多。即:next[j]越大,模式串向右滑动得越远,与主串进行比较的次数越少,时间复杂度就越低(时间效率)。next[j]=max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}模式串从第1位往右直到K-1位模式串从j的前一位往左经过K-1位想一想:如果主串和模式均为二进制码流,用KMP算法效果如何?T=‘abaabcac’再想一想:如果主串是外存中一个大文件,用KMP算法效果又如何?(2)next[j]具体怎么求?—即KMP算法的实现10计算Next[j]的方法:当j=1时,Next[j]=0;//Next[j