文档介绍：、基本概念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的下一字符起,重新与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<&&j<) { if([i]==[j]) {i++; j++; } else{ i=i-j+1;j=0; } }if(j==)v=i-;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能否利用已部分匹配过的信息而加快模式串的滑动速度?能!而且主串S的指针i不必回溯!最坏情况也能达到O(n+m)请看KMP算法!4尽量利用已经部分匹配的结果信息,尽量让i不要回溯,加快模式串的滑动速度。例:三、KMP算法1、KMP算法设计思想:S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’需要讨论两个问题:①如何由当前部分匹配结果确定模式向右滑动的新比较起点k?②模式应该向右滑多远才是高效率的?iiikkabaabckii5奇妙的结果:k仅与模式串T有关!请抓住部分匹配时的两个特征:两式联立可得:“T0…Tk-1”=‘Tj-k…Tj-1’S=‘ababcabcacbab’T=‘abcac’ik则T的k-1~0=S前i-1~i-k)位设目前打算与T的第k字符开始比较(1)(2)‘T0…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<k<jk是追求的新起点注意:j为当前已知的失配位置,我们的目标是计算新起点k。式中仅剩一个未知数k,理论上已可解!6根据模式串T的规律:“T0…Tk-1”=“Tj-k…Tj-1”由当前失配位置j(已知),可以归纳计算新起点k的表达式。next[j]=-1当j=0时max{k|0<k<j且‘T0…Tk-1’=‘Tj-k…Tj-1’}0其他情况注意:(1)k值仅取决于模式串本身而与相匹配的主串无关。(2)k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。(3)这里的两部分子串可以有部分重叠的字符,但不可以全部重叠。令k=next[j](k与j显然具有函数关系),则取T首与Tj处最大的相同子串新起点k怎么求?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|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况-10011201讨论:j=0时,next[j]≡-1;//属于“j=1”情况;j=1时,next[j]≡0;//找不到0<k<j的k,属于“其他情况”;j=2时,next[j]≡0;//只需查看‘T