【正文】 ， 實(shí)質(zhì)上還是一個(gè)無(wú)回溯的模式匹配算法 。應(yīng)該再右移，用 pnext[k]與 tj比較。 ?對(duì)任何模式 p， 若存在 next[i]（ i＝ 0， 1， … ，m1） ， 快速匹配算法如下： 在匹配過(guò)程中 ， 當(dāng) pi≠tj時(shí) ， 如果 next[i]大于等于 0， 將 p右移 i－ next[i]個(gè)字符 ， 從 tj與 p next[i]繼續(xù)比較 ， 否則從 tj＋ 1與 p0繼續(xù)比較下去 。 首先要為鏈串結(jié)構(gòu)和頭結(jié)點(diǎn)申請(qǐng)空間，創(chuàng)建一個(gè)空鏈表，這由算法 。 typedef struct SeqString *PSeqString。 ?字符串 s1中任意個(gè)連續(xù)的字符組成的子序列 s2被稱為是 s1的 子串 ，而稱 s1是 s2的 主串 。 特別地 ，空串是任意串的子串。 例如 ： 串 s = “abcdef”，用順序表示方式，假設(shè) s是 struct SeqString類型的變量，那么它的元素在數(shù)組中的存放方式如下圖所示： 創(chuàng)建空順序串 創(chuàng)建空串的方法與創(chuàng)建空順序表類似， 可有如下程序?qū)崿F(xiàn)： PSeqString createNullStr_seq( int m ) 求順序表示的串的子串 PSeqString subStr_seq(PSeqString s,int i,int j) 求從 s所指的順序串中第 i(i0)個(gè)字符開(kāi)始連續(xù)取 j個(gè)字符所構(gòu)成的子串。然后判斷所給參數(shù) i ，j的值是否合理， i ， j的取值應(yīng)為 i0， j0。 在已知 next數(shù)組的前提下，無(wú)回溯的匹配算法可以實(shí)現(xiàn)為： int pMatch(PSeqString t,PSeqString p, int *next) 算法分析： j的值在循環(huán)中只增不減 。這只要把第 7行修改為： if (pk!= pi) next[i]＝ k 。對(duì)于這個(gè)算法的改進(jìn)是巧上加巧 。 這種改進(jìn)是為了使 next[i]的值盡可能變得更小些 ，以便在匹配時(shí)更多地右移 。 j++}， 所以循環(huán)中 ， 執(zhí)行 i＝ next[i]的次數(shù) ， 不會(huì)超過(guò) i++的執(zhí)行次數(shù)加 1。 程序?qū)崿F(xiàn) 模式匹配 設(shè)有兩個(gè)串 t和 p： t = t0t1… tn1 p = p0p1… pm1 其中 1＜ m≤n（通常有 m n）。 然后判斷所給參數(shù) i ， j的值是否合理， i ， j的取值應(yīng)滿足 1≤ i ≤ sn， j0。 ?除 s本身之外， s的其它子串稱為 s的 真子串 。長(zhǎng)度為零的串稱為 空串 ，它不包括