第3章-字符串(存儲版)
【正文】 中 ， 執(zhí)行 i＝ next[i]的次數(shù) ， 不會超過 i++的執(zhí)行次數(shù)加 1。 ?由此可見 ， 若在匹配時發(fā)現(xiàn) pi≠tj， 即可直接地把 p右移 i－ k位 ， 并且只從 pk與 tj開始向右比較 。 這種改進是為了使 next[i]的值盡可能變得更小些 ，以便在匹配時更多地右移 。 但是作為一種抽象數(shù)據(jù)類型 ， 有它自己的操作 ， 在對串處理時 ， 要抓住它的特殊性 。對于這個算法的改進是巧上加巧 。 例子 ? t＝ aabcbabcaabcaababc n＝ 18， ? p＝ “ abcaababc”, m＝ 9。這只要把第 7行修改為： if (pk!= pi) next[i]＝ k 。 ?當右移量小于 i－ k時 ， 根據(jù) k的意義 ， 此時用長度大于 k的前后綴對齊 ， 比較結果必定不相等 。 在已知 next數(shù)組的前提下，無回溯的匹配算法可以實現(xiàn)為： int pMatch(PSeqString t,PSeqString p, int *next) 算法分析： j的值在循環(huán)中只增不減 。 否則必有某個 i（ 0≤i≤m1），使得 ti ≠pi，這時可將 p右移一個字符，用 p中字符從頭 p0開始與 t中字符 t1依次比較 . 如此反復執(zhí)行，直到下面兩種情況之一： ?到達某步時， ti = p0， ti+1 = p1， … ， ti+m1 = pm1，匹配成功，返回第一次出現(xiàn)的位置是從 t中第i+1個字符 ti開始 。然后判斷所給參數(shù) i ，j的值是否合理， i ， j的取值應為 i0， j0。 PStrNode link。 例如 ： 串 s = “abcdef”，用順序表示方式，假設 s是 struct SeqString類型的變量，那么它的元素在數(shù)組中的存放方式如下圖所示： 創(chuàng)建空順序串 創(chuàng)建空串的方法與創(chuàng)建空順序表類似， 可有如下程序實現(xiàn)： PSeqString createNullStr_seq( int m ) 求順序表示的串的子串 PSeqString subStr_seq(PSeqString s,int i,int j) 求從 s所指的順序串中第 i(i0)個字符開始連續(xù)取 j個字符所構成的子串。 String subStr (String s, int i, int j ) 在串 s中，求從串的第 i個字符開始連續(xù) j個字符所構成的子串。 特別地 ，空串是任意串的子串。第三章 字符串 首先介紹字符串的相關概念，引入字符串的抽象
高考資料相關推薦
鄂ICP備17016276號-1