算法分析與設(shè)計(jì)word版-資料下載頁(yè)
2025-06-05 11:49本頁(yè)面
【正文】 if ((jlen) == 1 || find[i] != find[jlen]) { rpr[i] = j len + 1。 break。 } } } for (k=1。 j(len1) amp。amp。 klen。 k++){ if (strncmp(find+i+k, find, lenk) == 0) { rpr[i] = 0 k。 break。 } } if (j(len1) amp。amp。 k == len) {rpr[i] = 0 len。 } } int delta_2[find_len]。 for (i=0。 ifind_len。 i++) delta_2[i] = find_len rpr[i]。 i = find_len 1。 j = find_len 1。 while (i text_len) { if (text[i] == find[j]) {i。 j。}else{ if (delta_1[text[i]] delta_2[j]) { i += delta_1[text[i]]。 } else { i += delta_2[j]。 } j = find_len 1。 } if (j == 1) return i+1。 } return 1。 } Sunday算法 ： 是 Daniel 1990年提出的字符串模式匹配。 該算法的主要思想： 在匹配過(guò)程中，模式串并不被要求一定要按從左向右進(jìn)行比較還是從右向左進(jìn)行比較，它在發(fā)現(xiàn)不匹配時(shí)，算法能跳過(guò)盡可能多的字符以進(jìn)行下一步的匹配，從而提高了匹配效率。 假設(shè)在發(fā)生不匹配時(shí) S[i]≠T[j]， 1≤i≤N， 1≤j≤M。此時(shí)已經(jīng)匹配的部分為 u，并假設(shè)字符串 u的長(zhǎng)度為 L。 很明顯， 該算法在字符串匹配時(shí)總共分為三種情況 : 1） S[L+i+1]肯定要參加下一輪的匹配，并且 T[M]至少要移動(dòng)到這個(gè)位置 (即模式串 T至少向右移動(dòng)一個(gè)字符的位置 )。 2） S[L+i+1]在模式串 T中沒(méi)有出現(xiàn)。這個(gè)時(shí)候模式串 T[0]移動(dòng)到 S[L+i+1]之后的字符的位置。 3） S[L+i+1]在模式串中出現(xiàn)。這里 S[L+i+1]從模式串 T的右側(cè)，即按 T[M1]、 T[M2]、?T[0]的次序查找。如果發(fā)現(xiàn) S[L+i+1]和 T中的某個(gè)字符相同，則記下這個(gè)位置，記為 k， 1≤ k≤ M，且 T[k]=S[L+i+1]。此時(shí)，應(yīng)該把模式串 T向右移動(dòng) Mk個(gè)字符的位置，即移動(dòng)到 T[k]和 S[L+i+1]對(duì)齊的位置。 該算法的主要實(shí)現(xiàn)代碼如下： int sunday(const char *text, const char *find) {if (text == 39。/039。 || find == 39。/039。) return 1。 char map[CHAR_MAX]。 int i。 int text_len = strlen(text)。 int find_len = strlen(find)。 if (text_len find_len) return 1。 for (i=0。 iCHAR_MAX。 i++)map[i] = find_len + 1。 for (i=0。 ifind_len。 i++) map[find[i]] = find_len i。 i = 0。 while (i = (text_len find_len)) {if (strncmp(find, text + i, find_len) == 0) return i。 else{ i += map[text[i + find_len]] 。} } return 1。 } 以上四種算法的程序運(yùn)行結(jié)果如下： 結(jié)合以上算法的理論分析和最終的程序運(yùn)行結(jié)果，對(duì)以上四種算法的效率進(jìn)行對(duì)比分析 結(jié)果 如下 表所示 ： 算法 預(yù)處理時(shí)間 時(shí)間復(fù)雜度 運(yùn)行時(shí)間 ms（規(guī)模 1000） Brute force算法 O(0) O(N*M) KMP O(N + M^2) O(N) Boyer Moore O(N + M^2) O(N) Sunday O(M) O(N*M) 由以上的理論和實(shí)驗(yàn)結(jié)果對(duì)比分析后，可以得出以下結(jié)論。 1） BF算法思路簡(jiǎn)單 ,但效率太低 。 2） KMP算法僅當(dāng)模式與主串之間存在許多“部分匹配” (即每趟比較若干字符后才發(fā)現(xiàn)不匹配 )的情況時(shí)才顯示出其時(shí)間優(yōu)越性 ,且算法中 next[j]的計(jì)算較難理解 。 3） BM算法考慮比較全面 ,包括了右移時(shí)的各種情況 ,但它使用了兩個(gè)數(shù)組 ,預(yù)處理時(shí)間花費(fèi)較大 。 4） Sunday算法思想跟 BM算法很相似，在匹配失敗時(shí)關(guān)注的是文本串中參加匹配的最末位字符的下一位字符。如果該字符沒(méi)有在匹配串中出現(xiàn)則直接跳過(guò)，即移動(dòng)步長(zhǎng) = 匹配串長(zhǎng)度 +1；否則，同 BM算法一樣其移動(dòng)步長(zhǎng) =匹配串中最右端的該字符到末尾的距離 +1。對(duì)于短模式串的匹配問(wèn)題，該算法執(zhí)行速度較快。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1