4.4串的模式匹配算法 基本概念 1、模式匹配(定位) 设有主串S和子串T(将S称为目标串,将T称为模式 串),在主串S中,从位置 start开始查找,如若在主 串S中找到一个与子串T相等的子串,则返回T的第 个字符在主串中的位置,否则返回-1。 2、算法目的 确定主串中所含子串第一次出现的位置(定位) 3、算法种类 B算法(又称古典的、经典的、朴素的、穷举的) KMP算法
1 4.４ 串的模式匹配算法 一、基本概念 1、模式匹配（定位） 设有主串S和子串T（将S称为目标串，将T称为模式 串），在主串S中，从位置start开始查找，如若在主 串S中找到一个与子串T相等的子串，则返回T的第一 个字符在主串中的位置，否则返回-1。 2、算法目的 确定主串中所含子串第一次出现的位置（定位） 3、算法种类 BF算法 （又称古典的、经典的、朴素的、穷举的） KMP算法
Brute-Force算法 1、 Brute- Force算法的设计思想 将主串S的第一个字符和模式T的第1个字符比较, 若相等,继续逐个比较后续字符; 若不等,从主串S的下一字符起,重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式相等。返回值为S 中与T匹配的子序列第一个字符的序号,即匹配成功 否则,匹配失败,返回值-1。 2、 Brute- Force算法的实现 typedef struct i char str MaxSize; int length sTring;
2 二、Brute-Force算法 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 BFlndex(string S, int start, String T t int i=start,j=0,V: while(i<slength &&j< Tlength) i if(S str1==Tstr[D i++,j++, else +1;j=0 if =T length)Vi-Tlength else v=-1 return v
3 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(m) 最好的情况是:一配就中!只比较了m次。 最恶劣情况是:主串前面n-m个位置都部分匹配到子串的最后 一位,即这nm位比较了m次,别忘了最后m位也各比较了 次,还要加上m!所以总次数为:(n-m)*m+m=(n- 影苦莉用己部分匹配过的信息而加快模式串的滑动速度? 能!而且主串S的指针必回溯!最坏情况也能达到o(n+m) 请看KMP算法!
4 3、BF算法的时间复杂度 讨论： 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况 下需要比较字符的总次数为(n-m+1)*m＝O(n*m) 最好的情况是：一配就中！ 只比较了m次。 最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后 一位，即这n-m位比较了m次，别忘了最后m位也各比较了 一次，还要加上m！所以总次数为：(n-m)*m+m ＝(nm+1)*m 能否利用已部分匹配过的信息而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m) 请看KMP算法！
KMP算法 KMP算法设计思想 尽量利用已经部分匹配的结果信息,尽量让不要回溯,加快模 式串的滑动速度。 例 a b a bca bcacba b' s=a b a b c a b ac b a b T=“ a bcac T=‘ a bc a c S=“ a ba bc a bc acb a b T=abc c k 需要讨论两个问题 ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k? ②模式应该向右滑多远才是高效率的?
5 尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模 式串的滑动速度。 例： 三、KMP算法 １、KMP算法设计思想： S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ ② 模式应该向右滑多远才是高效率的? i i i k k a b a a b c k i i