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