下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、Tre樹(字典樹)數(shù)據(jù)結(jié)構(gòu)詳解(圖解)及模板了解這個(gè)數(shù)據(jù)結(jié)構(gòu)之前我們需要了解它能被用來(lái)做什么字典樹又稱單詞查找樹,Tire樹,是一種樹形結(jié)構(gòu),是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì),排序和保存大量的字符串(但不僅限于字符串),所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是:利用字符串的公共前綴來(lái)減少查詢時(shí)間,最大限度地減少無(wú)謂的字符串比較,查詢效率比哈希樹高。說(shuō)到底,字典樹就是用來(lái)查詢公共前綴的一個(gè)工具,延伸的話可以用來(lái)進(jìn)行串匹配,詞頻統(tǒng)計(jì)等,也是學(xué)AC自動(dòng)機(jī)的前置技能.所謂的字典樹,其實(shí)就是一個(gè)n叉樹我們對(duì)于每個(gè)字母,如果有公共前綴的,我們找到它的前綴,在后面不同的部分建立不同的子節(jié)點(diǎn),
2、比如說(shuō)apple,appear,appxy三個(gè)不同的單詞,公共前綴為app,所以建樹如下:那么問(wèn)題來(lái)了,單詞的第一個(gè)字母不止A啊,應(yīng)該怎么辦?其實(shí)不難,學(xué)過(guò)二分圖的應(yīng)該能想出來(lái):設(shè)置一個(gè)超級(jí)源點(diǎn),我們?cè)诘谝粋€(gè)字母上面再設(shè)一個(gè)超級(jí)源點(diǎn),這樣計(jì)算的時(shí)候不考慮他就行了,這樣第一層就可以和下面的子節(jié)點(diǎn)一樣建立了如圖所示(ps:此圖有誤,apply應(yīng)該為appxy)又是喜(sang)聞(xin)樂(lè)(bing)見(jiàn)(kuang)的代碼環(huán)節(jié)了個(gè)人由于ACM的原因,就只放數(shù)組實(shí)現(xiàn)的板子了,(反正懂原理了指針版的也挺簡(jiǎn)單的)由于數(shù)組不能動(dòng)態(tài)開(kāi)內(nèi)存,所以我們就得采用模擬的形式了,這里其實(shí)用了一點(diǎn)并查集的思想,各位客
3、官看下圖由于不能動(dòng)態(tài)分配內(nèi)存,同時(shí)字典樹又是比較耗費(fèi)空間的,所以我們的內(nèi)存分配盡可能大,開(kāi)一個(gè)二維數(shù)組iremaxn26然后tireij=k代表編號(hào)為i的節(jié)點(diǎn)的第j個(gè)孩子是編號(hào)為k的節(jié)點(diǎn),這里的j通常指當(dāng)前位的字母A-Z然后關(guān)于編號(hào),我們這里的存樹方式是:如果要生成新節(jié)點(diǎn),則編號(hào)+,否則編號(hào)不動(dòng),所以如上圖,APPLY的對(duì)應(yīng)編號(hào)應(yīng)該為1,2,3,4,10,11;同時(shí)有:tire1A-A=2;tire2P-A=3;tire3P-A=10;tire10X-A=11;tire11Y-A=0;這樣,查找的時(shí)候利用并查集的思想不斷向下查找即可代碼如下/*頭文件可以忽略,只是一些常用的宏*/#includ
4、e#include#include#include#include#include#include#include#include#include#include#define_mem(a,b)memset(a,0,(b+3)2)#definefori(a)for(inti=0;ia;i+)#defineforj(a)for(intj=0;ja;j+)#defineifor(a)for(inti=1;i=a;i+)#defineifor(a)for(inti=1;i=a;i+)#definejfor(a)for(intj=1;j=a;j+)#definemem(a,b)memset(a,b,s
5、izeof(a)#defineINfreopen(in.txt,r,stdin)#defineOUTfreopen(out.txt,w,stdout)#defineIOdoios:sync_with_stdio(false);cin.tie(0);cout.tie(0);while(0)#definemp(a,b)make_pair(a,b);usingnamespacestd;typedeflonglongll;constintmaxn=1e5;constintINF=0 x3f3f3f3f;constintinf=0 x3f;constdoubleEPS=1e-7;constdoubleP
6、i=acos(-1);constintMOD=1e9+7;intTiremaxn26;charstr2000005;boolvmaxn;strings;intcnt=1;建樹,每輸入一個(gè)單詞到s里面就調(diào)用_insert()就好void_insert()introot=0;fori(s.size()intnext=si-A;if(!Tirerootnext)Tirerootnext=+cnt;root=Tirerootnext;vroot=true;/這里用了一個(gè)標(biāo)記數(shù)組表示該點(diǎn)存在一個(gè)完整的單詞比如說(shuō)app和apple在最后一個(gè)p的位置就會(huì)被標(biāo)記true查找最長(zhǎng)公共前綴int_find(charbufs,intleng)introot=0;intcns=0;intnext;intres=0;
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 錫冶煉廠的生產(chǎn)計(jì)劃與生產(chǎn)調(diào)度考核試卷
- 銻冶煉資源高效利用與可持續(xù)發(fā)展考核試卷
- 牧業(yè)機(jī)械化飼料作物種植技術(shù)與推廣考核試卷
- 非木竹材林產(chǎn)品采集與林業(yè)科技創(chuàng)新應(yīng)用考核試卷
- 印刷業(yè)產(chǎn)品設(shè)計(jì)創(chuàng)意與實(shí)現(xiàn)考核試卷
- 九年教研組工作計(jì)劃
- 倉(cāng)儲(chǔ)部門崗位職責(zé)
- 交通事故責(zé)任認(rèn)定
- 樂(lè)器清潔刷商業(yè)發(fā)展計(jì)劃書
- 修面刷架相關(guān)項(xiàng)目實(shí)施方案
- Unit-3-UI-The-Road-to-Success-高中英語(yǔ)新教材外研版(選擇性必修第一冊(cè))
- 部編2024版歷史七年級(jí)上冊(cè)第三單元《第13課 東漢的興衰》教案
- 腦卒中后吞咽障礙患者進(jìn)食護(hù)理團(tuán)體標(biāo)準(zhǔn)
- 期中 (試題) -2024-2025學(xué)年譯林版(三起)英語(yǔ)四年級(jí)上冊(cè)
- 蘇教版(2024)科學(xué)一年級(jí)上冊(cè)教學(xué)設(shè)計(jì)(附教材目錄)
- 2024人教版道法七年級(jí)上冊(cè)第二單元:成長(zhǎng)的時(shí)空大單元整體教學(xué)設(shè)計(jì)
- 【課件】Unit+3(單元解讀課件)七年級(jí)英語(yǔ)上冊(cè)(人教版2024)
- RB/T 121-2023能源管理體系建材企業(yè)認(rèn)證要求(不含水泥、玻璃、陶瓷)
- 《別了“不列顛尼亞”》《縣委書記的榜樣-焦裕祿》對(duì)比閱讀+課件++2023-2024學(xué)年統(tǒng)編版高中語(yǔ)文選擇性必修上冊(cè)
- 2024年注冊(cè)安全工程師考試題庫(kù)及完整答案【歷年真題】
- 鄉(xiāng)村醫(yī)生預(yù)防接種培訓(xùn)課件
評(píng)論
0/150
提交評(píng)論