首頁 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實(shí)用文檔 求職招聘 論文下載
2011中考 | 2011高考 | 2012考研 | 考研培訓(xùn) | 在職研 | 自學(xué)考試 | 成人高考 | 法律碩士 | MBA考試
MPA考試 | 中科院
四六級 | 職稱英語 | 商務(wù)英語 | 公共英語 | 托福 | 雅思 | 專四專八 | 口譯筆譯 | 博思 | GRE GMAT
新概念英語 | 成人英語三級 | 申碩英語 | 攻碩英語 | 職稱日語 | 日語學(xué)習(xí) | 法語 | 德語 | 韓語
計算機(jī)等級考試 | 軟件水平考試 | 職稱計算機(jī) | 微軟認(rèn)證 | 思科認(rèn)證 | Oracle認(rèn)證 | Linux認(rèn)證
華為認(rèn)證 | Java認(rèn)證
公務(wù)員 | 報關(guān)員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問 | 導(dǎo)游資格
報檢員 | 教師資格 | 社會工作者 | 外銷員 | 國際商務(wù)師 | 跟單員 | 單證員 | 物流師 | 價格鑒證師
人力資源 | 管理咨詢師考試 | 秘書資格 | 心理咨詢師考試 | 出版專業(yè)資格 | 廣告師職業(yè)水平
駕駛員 | 網(wǎng)絡(luò)編輯
衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護(hù)士
會計從業(yè)資格考試會計證) | 經(jīng)濟(jì)師 | 會計職稱 | 注冊會計師 | 審計師 | 注冊稅務(wù)師
注冊資產(chǎn)評估師 | 高級會計師 | ACCA | 統(tǒng)計師 | 精算師 | 理財規(guī)劃師 | 國際內(nèi)審師
一級建造師 | 二級建造師 | 造價工程師 | 造價員 | 咨詢工程師 | 監(jiān)理工程師 | 安全工程師
質(zhì)量工程師 | 物業(yè)管理師 | 招標(biāo)師 | 結(jié)構(gòu)工程師 | 建筑師 | 房地產(chǎn)估價師 | 土地估價師 | 巖土師
設(shè)備監(jiān)理師 | 房地產(chǎn)經(jīng)紀(jì)人 | 投資項目管理師 | 土地登記代理人 | 環(huán)境影響評價師 | 環(huán)保工程師
城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價師 | 安全評價師 | 電氣工程師 | 注冊測繪師 | 注冊計量師
繽紛校園 | 實(shí)用文檔 | 英語學(xué)習(xí) | 作文大全 | 求職招聘 | 論文下載 | 訪談 | 游戲
您現(xiàn)在的位置: 考試吧(Exam8.com) > 軟件水平考試 > 復(fù)習(xí)資料 > 程序員資料 > 正文

2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理(16)

考試吧提供了“2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理”,供考生參考。

  7、求一個串最多由哪個串復(fù)制若干次得到 PKU2406

  具體的問題描述請參考PKU2406.這個問題可以用KMP解決,而且效率比后綴數(shù)組好。

  利用后綴數(shù)組直接解決本題也很困難(主要是,就算二分答案,也難以解決轉(zhuǎn)變而成的判定性問題。上題也是),但可以同過枚舉模板串的長度k(模板串指被復(fù)制的那個串)將問題變成一個后綴數(shù)組可以解決的判定性問題。首先判斷k能否被n整除,然后只要看lcp(1,k+1)(實(shí)際在用c寫程序時是lcp(0,k))是否為n-k就可以了。

  為什么這樣就行了呢?這要充分考慮到后綴的性質(zhì)。當(dāng)lcp(1,k+1)=n-k時,后綴k+1是后綴1(即整個字符串)的一個前綴。(因?yàn)楹缶Yk+1的長度為n-k)那么,后綴1的前k個字符必然和后綴k+1的前k個字符對應(yīng)相同。而后綴1的第k+1..2k個字符,又相當(dāng)于后綴k+1的前k個字符,所以與后綴1的前k個字符對應(yīng)相同,且和后綴k的k+1..2k又對應(yīng)相同。依次類推,只要lcp(1,k+1)=n-k,那么s[1..k]就可以通過自復(fù)制n/k次得到整個字符串。找出k的最小值,就可以得到n/k的最大值了。

  8、求兩個字符串的最長公共子串。Pku2774、Ural1517

  首先區(qū)分好“最長公共子串”和“最長公共子序列”。前者的子串是連續(xù)的,后者是可以不連續(xù)的。

  對于兩個字符串的問題,一般情況下均將它們連起來,構(gòu)造height數(shù)組。然后,最長公共子串問題等價于后綴的最長公共前綴問題。只不過,并非所有的lcp值都能作為問題的答案。只有當(dāng)兩個后綴分屬兩個字符串時,它們的lcp值才能作為答案。與問題3一樣,本題的答案必然是某個height值,因?yàn)閘cp值是某段height值中的最小值。當(dāng)區(qū)間長度為1時,lcp值等于某個height值。所以,本題只要掃描一遍后綴,找出后綴分屬兩個字符串的height值中的最大值就可以了。判斷方法這里就不說明了,留給大家自己思考...

  9、重復(fù)次數(shù)最多的重復(fù)子串 SPOJ 687,Pku3693

  難度比較大的一個問題,主要是羅穗騫的論文里的題解寫得有點(diǎn)含糊不清。題目的具體含義可以去參考Pku3693.

  又是一題難以通過二分枚舉答案解決的問題(因?yàn)橐蟮氖侵貜?fù)次數(shù)),所以選擇樸素枚舉的方法。先枚舉重復(fù)子串的長度k,再利用后綴數(shù)組來求長度為k的子串最多重復(fù)出現(xiàn)多少次。注意到一點(diǎn),假如一個字符串它重復(fù)出現(xiàn)2次(這里不討論一次的情況,因?yàn)槟鞘潜厝坏?,那么它必然包含s[0],s[k],s[2*k]...之中的相鄰的兩個。所以,我們可以枚舉一個數(shù)i,然后判斷從i*k這個位置起的長度為k的字符串能重復(fù)出現(xiàn)多少次。判斷方法和8中的相似,lcp(i*k,(i+1)*k)/k+1。但是,僅僅這樣會忽略點(diǎn)一些特殊情況,即重復(fù)子串的起點(diǎn)不在[i*k]位置上時的情況。這種情況應(yīng)該怎么求解呢?看下面這個例子:

  aabababc

  當(dāng)k=2,i=1時,枚舉到2的位置,此時的重復(fù)子串為ba(注意第一位是0),lcp(2,4)=3,所以ba重復(fù)出現(xiàn)了2次。但實(shí)際上,起始位置為1的字符串a(chǎn)b出現(xiàn)次數(shù)更多,為3次。我們注意到,這種情況下,lcp(2,4)=3,3不是2的整數(shù)倍。說明當(dāng)前重復(fù)子串在最后沒有多重復(fù)出現(xiàn)一次,而重復(fù)出現(xiàn)了部分(這里是多重復(fù)出現(xiàn)了一個b)。如果我這樣說你沒有看懂,那么更具體地:

  sa[2]=bababc

  sa[4]=babc

  lcp=bab

  現(xiàn)在注意到了吧,ba重復(fù)出現(xiàn)了兩次之后,出現(xiàn)了一個b,而a沒有出現(xiàn)。那么,不難想到,可以將枚舉的位置往前挪一位,這樣這個最后的b就能和前面的一個a構(gòu)成一個重復(fù)子串了,而假如前挪的一位正好是a,那么答案可以多1。所以,我們需要求出a=lcp(i*k,(i+1)*k)%n,然后向前挪k-a位,再用同樣的方法求其重復(fù)出現(xiàn)的長度。這里,令b=k-a,只需要lcp(b,b+k)>=k就可以了。實(shí)際上,lcp(b,b+k)>=k時,lcp(b,b+k)必然大于等于之前求得的lcp值,而此時答案的長度只加1。沒有理解的朋友細(xì)細(xì)體會下上圖吧。

上一頁  1 2 3 4 5 下一頁
  相關(guān)推薦:

  軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

  2011年上半年軟考報名時間及方式匯總

  軟考程序員考試歷年真題匯總(2007年-2010年)

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請注明出處。