串的匹配算法.ppt

《串的匹配算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.４串的模式匹配算法一、基本概念1、模式匹配（定位）设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。2、算法目的确定主串中所含子串第一次出现的位置（定位）3、算法种类BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法1二、Brute-Force算法1、Brute-Force算法的设计思想：将主串S的第一个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下

2、一字符起，重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值–1。2、Brute-Force算法的实现typedefstruct{charstr[MaxSize];intlength;}String;2intBFIndex(StringS,intstart,StringT){inti=start,j=0,v;while(i

3、;}else{i=i-j+1;j=0;}}if(j==T.length)v=i-T.length;elsev=-1;returnv;}33、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能否利用已部分匹配过的信息而加快

4、模式串的滑动速度？能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m)请看KMP算法！4尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。例：三、KMP算法１、KMP算法设计思想：S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是高效率的?iiikkabaabckii5奇妙的结果：k仅与模式串T

5、有关！请抓住部分匹配时的两个特征：两式联立可得：“T0…Tk-1”=‘Tj-k…Tj-1’S=‘ababcabcacbab’T=‘abcac’ik则T的k-1～０＝S前i-1～i-k)位设目前打算与T的第k字符开始比较(1)(2)‘T０…Tk-1’则T的j-1～j-k位＝S前i-1～i-k)位ikjS=‘ababcabcacbab’T=‘abcac’刚才肯定是在S的i处和T的第j字符处失配‘Tj-k…Tj-1’截取一段，但k有限制，0

6、未知数k，理论上已可解！6根据模式串T的规律：“T0…Tk-1”=“Tj-k…Tj-1”由当前失配位置j(已知)，可以归纳计算新起点k的表达式。next[j]＝-1当j＝0时max{k

7、0

8、7next[j]函数表征着模式T中最大相同前缀子串和后缀子串（真子串）的长度。可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。再想一想：如果主串是外存中一个大文件，用KMP算法效果又如何？8从两头往中间比较例：模式串T：abaabcac可能失配位j：01234567新匹配位k=next[j]:next[j]＝0当j＝1时max{k

9、1

10、且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况-10011201讨论：j=0时,next[j]≡-1；//属于“j=1”情况;j=1时,next[j]≡0；//找不到0