您好,登錄后才能下訂單哦!
復習串的樸素模式匹配算法
模式匹配 :
子串定位運算,在主串中找出子串出現的位置。
在串匹配中,將主串 S 稱為目標(串),子串 T 稱為模式(串)。如果在主串 S 中能夠找到子串 T, 則稱匹配成功,返回 第一個 和 子串 T 中 第一個字符 相等 的 字符 在主串 S 中的 序號,否則,稱匹配失敗,返回 0。
算法思想:
從主串 S 的第 pos 個字符起和模式 T 的第一個字符比較之,若相同,則兩者順次的去比較后續的每一個字符,否則從主串 S 的下一個字符起再重新和模式 T 的字符比較之。 (為什么說它樸素,就是因為笨,因子串和主串的每躺比較,當發現匹配不對,則主串的指針要回溯到上次開始比較的字符處的下一個字符處,去重新比一遍!費勁)。
詳細圖解;
給定兩個字符串,S 和 T,長度已知。
-》
初始 ab 相同,可以順次比較,當3處,不匹配。則j 回溯到T1處,i 回到S 的下一個字符 S2處,從新開始和 T1比較。
-》
b 和 a又不匹配,j 回到1處(位置不變),i 回到下一個字符,也就是3處,繼續比,匹配,順次比較之。直到下面;
模式串的 j再次回溯到1,i 到4,繼續比較,不匹配,T 的 j 繼續回溯1,S的 i 繼續到下一個字符,繼續比較,直到 i=6,匹配
繼續順次比較,直到 T 比完,也就是在 j=5,i=10之后,j、i 繼續++的時候,要判斷出比完了,如圖。這是整個過程。算法重要的是思想,理解思想,是第一步,腦子里有清晰的思路和完美的情景再現,那么代碼實現都是水到渠成的事情。
用代碼編寫如下:
1 int getLength(char *str) 2 { 3 int i = 0; 4 5 while ('\0' != str[i]) { 6 i++; 7 } 8 9 return i;10 }11 12 int strCompare(char *strMain, char *strSub, int index)13 {14 int iMain = index;15 int jSub = 0;16 int lenMain = getLength(strMain);17 int lenSub = getLength(strSub);18 19 while ((iMain >= 0 && iMain <= lenMain - 1) && ((jSub >= 0 && jSub <= lenSub - 1))){20 if (strMain[iMain] == strSub[jSub]) {21 iMain++;22 jSub++;23 }else{24 iMain = iMain - jSub + 1;//回到主串的下一個位置起,開始比較,每次重新開始順次比較, ij 走的長度是一樣的,如果從0開始,那么相減之后,故+1到下一位,如果是從1開始存,那么+2到下一位。25 jSub = 0;26 }27 }28 //如果匹配 ok,肯定子串先比完。29 if (jSub > lenSub - 1) {30 return iMain - lenSub;//得到的就是匹配 ok 后,主串里第一個和模式串第一個字符匹配的字符的位置31 }else{32 return 0;//匹配失敗33 }34 }35 36 int main(int argc, const char * argv[]) {37 char *str1 = "sawtsafvda";38 char *str2 = "safv";39 40 int i = strCompare(str1, str2, 0);41 42 printf("%d\n", i);43 44 return 0;45 }
4
Program ended with exit code: 0
分析時間復雜度
最壞的時候,最后匹配成功,比如,0000000000001 和 00001 ,比較每次都在00001的1開始不匹配,指針回溯到開頭,主串也回溯 i-j+1,若模式子串的長度是m,目標串的長度是n,這時最壞的情況是每遍比較都在最后出現不等,即每遍最多比較m次,最多比較n-m+1遍,總的比較次數最多為m(n-m+1),因此樸素的模式匹配算法為 o(m*n),雖然,樸素的模式匹配,時間復雜度比較大,但是實際中,一般情況(除非模式串和主串之間存在很多的部分匹配的時候,因為此時每遍需要比較的次數很多,相乘不能近似),真正的執行時間是近似于o(n+m )的,故當今仍然有他的用處!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。