数据结构第4章详解.ppt

位置：字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。  A=‘China Beijing’, B=‘Beijing’, C=‘China’, 则它们的长度分别为13、7和5。B和C是A的子串, B在A中的位置是7, C在A中的位置是1。 串相等：当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等, 并且每个对应位置的字符都相等时才相等。 空格串：由一个或多个空格组成的串。与空串不同。 串长的表示： ①以下标为0的数组分量存放串的实际长度； ②串值后加入一个不计入串长的结束标记字符，C中“\0”表串值的终结，其ASCⅡ码值为0。 作业： 4.1 4.18 Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是: 从目标串s=“s1s2…sn”的第一个字符开始和模式串t=“t1t2…tm”中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从目标串s的第i个字符开始,每个字符依次和模式串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回0。 子串定位int Index( SString S, SString T, int pos) { i= pos; j = 1; while( i=S[0] j=T[0]){ if(S[i] == T[j]){ ++i; ++j; } else{ i = i-j+2; j =1; } } if(jT[0]) return i-T[0]; else return 0; } 朴素模式匹配算法的时间复杂度 主串长n； 子串长m。可能匹配成功的位置（1 ~ n-m+1)。 ①最好的情况下， 第i个位置匹配成功，比较了（i-1+m）次，平均比较次数： 最好情况下算法的平均时间复杂度O(n+m)。 ②最坏的情况下， 第i个位置匹配成功，比较了（i*m）次，平均比较次数： 设nm，最坏情况下的平均时间复杂度为O(n*m)。 2. 模式匹配的改进算法-KMP算法 KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。 s1 s2 s3…si-j+1 si-j+2…si-2 si-1 si si+1 ‖ ‖ ‖ ‖ ≠ p1 p2 … pj-2 pj-1 pj pj+1 ‖ ‖ p1 … pk-1 pk pk+1 如何求next函数值 1. next[1] = 0;表明主串从下一字符si+1起和模式串重新开始匹配。i = i+1; j = 1; 2. 设next[j] = k，则next[j+1] = ? ①若pk=pj，则有“p1…pk-1pk”=“pj-k+1…pj-1pj” ，如果在 j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。 ②若pk≠pj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。 p1 p2…pj-k+1…pj-1 pj pj+1 next[j]=k ‖ ‖ ≠ p1 … pk-1 pk pk+1 next[k]=k’ p1…… pk’ pk’+1 next[k’]=k” p1… pk’’ pk’’+1 next[k’’]=k’’’ j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 模式串 a b c a a b b c a b c a a b d a b void get_next(SString T, int next[]) { i= 1; next[1] = 0; j = 0; while( iT[0]