南阳网站制作公司,东莞网站建设 手机壳,游戏网站开发过程,莱芜都市网帖子怎么删除数据结构c语言版严蔚敏清华大学出版社第四章串模式匹配(定位) 设有主串S和子串T(将S称为目标串#xff0c;将T称为模式串)#xff0c;在主串S中#xff0c;从位置start开始查找#xff0c;如若在主串S中找到一个与子串T相等的子串#xff0c;则返回T的第一个字符在主串中的…数据结构c语言版严蔚敏清华大学出版社第四章串模式匹配(定位) 设有主串S和子串T(将S称为目标串将T称为模式串)在主串S中从位置start开始查找如若在主串S中找到一个与子串T相等的子串则返回T的第一个字符在主串中的位置否则返回-1。 算法目的 确定主串中所含子串第一次出现的位置(定位) 算法种类 BF算法 (又称古典的、经典的、朴素的、穷举的) KMP算法 Brute-Force算法的设计思想 将主串S的第一个字符和模式T的第1个字符比较 若相等继续逐个比较后续字符 若不等从主串S的下一字符起重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号即匹配成功。 否则匹配失败返回值 –1。 BF算法的时间复杂度 讨论 若n为主串长度m为子串长度则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m1)*mO(n*m) 最好的情况是一配就中 只比较了m次。 最恶劣情况是主串前面n-m个位置都部分匹配到子串的最后一位即这n-m位比较了m次别忘了最后m位也各比较了一次还要加上m所以总次数为(n-m)*mm (n-m1)*m KMP算法设计思想 设s为主串t为模式串设i为主串s当前比较字符的下标j为模式串t当前比较字符的下标令i和j的初值为。当si tj时i和j分别增1再继续比较否则 i不变j改变为next[j]值(即模式串右滑)后再继续比较。依次类推直到出现下列两种情况之一一是 j退回到某个jnext[j]值时有si tj 则 i和j分别增1后再继续比较二是j退回到j-1时令主串和子串的下标各增1随后比较si1和t0 。这样的循环过程一直进行到变量大于等于S.length或变量j大于等于T.length时为止。 KMP算法的时间复杂度 注意由于BF算法在一般情况下的时间复杂度也近似于O(nm)所以至今仍被广泛采用。 第四趟匹配 ababcabcacbab abcac 第五趟匹配 ababcabcacbab a 第六趟匹配 ababcabcacbab abcac i4 j1 i5 j1 i11 j6 能否利用已部分匹配过的信息而加快模式串的滑动速度 能而且主串S的指针i不必回溯最坏情况也能达到O(nm) 请看KMP算法 当模式串为,主串为’00000000000000000000000000000000000000000000000000001’时,整个匹配过程中指针i需回溯45次. a b a 尽量利用已经部分匹配的结果信息尽量让i不要回溯加快模式串的滑动速度。 例 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 c k i i 2、KMP算法 T‘a b c a c’ S‘a b a b c a b c a c b a b’ i k S‘a b a b c a b c a c b a b’ T‘a b c a c’ i k 奇妙的结果 k 仅与模式串T有关 请抓住部分匹配时的两个特征 两式联立可得“T0…Tk-1”‘Tj-k …Tj-1’ 则T的k-1S前i-1i-k)位 设目前打算与T的第k字符开始比较 (1) (2) ‘T … Tk-1’ 则T的j-1j-k位 S前i-1i-k)位 刚才肯定是在S的i处和T的第j字符 处失配 ‘Tj-k …Tj-1’ 截取一段但k有限制0
