算法合集之《trie圖的構(gòu)建、活用與改進(jìn)》(文件)
【正文】 出發(fā)走step步到結(jié)點(diǎn)x的走法數(shù)，則容易寫出下面的偽代碼：fillchar(count,sizeof(count),0)。for 安全圖中每個(gè)結(jié)點(diǎn)x doinc(ans,count[m,x])。同樣，它的有向性也可以成為動(dòng)態(tài)規(guī)劃劃分階段的依據(jù)。再給出一段文本，文本的每一行可能包含除chr(0),chr(10),chr(13)外的任何字符。詞典的大小不超過(guò)100KB，每個(gè)不良單詞的長(zhǎng)度不超過(guò)10000?！据敵觯?biāo)準(zhǔn)輸出）】若文本中有不良單詞，輸出一行兩個(gè)整數(shù)，表示不良單詞第一次出現(xiàn)的行和列，用一個(gè)空格隔開(kāi)。【內(nèi)存限制】5000KB。我們看到，在本題中，算法的瓶頸在于從每個(gè)結(jié)點(diǎn)出發(fā)的邊數(shù)。函數(shù)內(nèi)部的程序其實(shí)完全是按照加邊的原則編寫的：如果x本來(lái)就有c孩子，那么就返回這個(gè)孩子；如果x沒(méi)有c孩子，根據(jù)加邊的原則，函數(shù)應(yīng)該返回x的后綴結(jié)點(diǎn)的c孩子，也就是令x為它的后綴結(jié)點(diǎn)，重新執(zhí)行函數(shù)。其實(shí)，算法的時(shí)間復(fù)雜度為O(L1+L2)，數(shù)量級(jí)并沒(méi)有受到影響，只是增加了一點(diǎn)常數(shù)系數(shù)。若b是trie樹(shù)中a結(jié)點(diǎn)的一個(gè)孩子，那么b的后綴結(jié)點(diǎn)的深度至多比a的后綴結(jié)點(diǎn)大1。178。綜上所述，改進(jìn)后的trie圖的時(shí)間復(fù)雜度為O(L1+L2)。對(duì)于什么樣的題目需要用改進(jìn)的trie圖，在此作一下總結(jié)：178。 用到圖中每一條邊的題目（如第二部分中提到的拓?fù)渑判?、?dòng)態(tài)規(guī)劃等）：一般用未改進(jìn)的trie圖。附：《病毒》一題的程序：《字謎》一題的程序可以在。如果字符集較大甚至無(wú)限（漢字的多模式匹配系統(tǒng)的字符集幾乎可以認(rèn)為是無(wú)限的），就必須使用改進(jìn)的trie圖。第二部分中的《字謎》一題到此也得到了圓滿解決。因?yàn)楣鈽?biāo)如果往下走，它只能走1步，所以若把光標(biāo)經(jīng)過(guò)的位置的深度也排成一個(gè)數(shù)列，這個(gè)數(shù)列與上一段提到的數(shù)列具有相同的性質(zhì)：增長(zhǎng)是緩慢的。當(dāng)后一項(xiàng)減前一項(xiàng)的差小于1時(shí)，child函數(shù)就會(huì)被重復(fù)執(zhí)行。我們分別討論增加的這點(diǎn)時(shí)間對(duì)建圖過(guò)程和文本檢查過(guò)程所需時(shí)間的影響：178。經(jīng)過(guò)這樣的處理，算法的空間復(fù)雜度由O(L1a)降到了O(L1)，對(duì)于本題來(lái)說(shuō)是足夠低的了。Trie樹(shù)中的邊自然是要存儲(chǔ)的（用左孩子右兄弟表示法），但新建的邊則不必存儲(chǔ)。與例1相比，這道題的字符集大得多，如果直接建trie圖，從每個(gè)結(jié)點(diǎn)出發(fā)要建253條邊，而結(jié)點(diǎn)數(shù)最多為100000，嚴(yán)重超內(nèi)存?！緲永斎搿?robProblem1Internet Problem Solving Contest【樣例輸出】1 10【注意】樣例中“第一次出現(xiàn)”的不良單詞是Problem而不是rob，雖然rob比Problem先結(jié)束。接下來(lái)m行是文本。【輸入（標(biāo)準(zhǔn)輸入）】第一行為一個(gè)整數(shù)n(1=n=10000)，表示不良單詞的個(gè)數(shù)。下面探討這個(gè)問(wèn)題的解決方法。我們看到，trie圖的安全圖上還是大有文章可做的。for step:=1 to m dofor 安全圖中每條邊(i,j) do inc(count[step,j],count[step1,i])?！据敵觯?biāo)準(zhǔn)輸出）】一個(gè)整數(shù)，表示長(zhǎng)度為m且不含不良單詞的字符串的數(shù)目?！纠?】Censored!（題目來(lái)源：Ural 1158）【題目描述】已知一個(gè)由n(1=n=50)個(gè)字符組成的字符集及p(0=p=10)個(gè)不良單詞（長(zhǎng)度均不超過(guò)10），求長(zhǎng)度為m(1=m=50)且不含
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1