題目1337【例3-2】單詞查找樹題目描述在進(jìn)行文法分析的時(shí)候通常需要檢測(cè)一個(gè)單詞是否在我們的單詞列表里。為了提高查找和定位的速度通常都畫出與單詞列表所對(duì)應(yīng)的單詞查找樹其特點(diǎn)如下1根結(jié)點(diǎn)不包含字母除根結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都僅包含一個(gè)大寫英文字母2從根結(jié)點(diǎn)到某一結(jié)點(diǎn)路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列稱為該結(jié)點(diǎn)對(duì)應(yīng)的單詞。單詞列表中的每個(gè)單詞都是該單詞查找樹某個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的單詞3在滿足上述條件下該單詞查找樹的結(jié)點(diǎn)數(shù)最少。4例下圖左邊的單詞列表就對(duì)應(yīng)于右邊的單詞查找樹。注意對(duì)一個(gè)確定的單詞列表請(qǐng)統(tǒng)計(jì)對(duì)應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)包含根結(jié)點(diǎn)。輸入為一個(gè)單詞列表每一行僅包含一個(gè)單詞和一個(gè)換行/回車符。每個(gè)單詞僅由大寫的英文字母組成長(zhǎng)度不超過63個(gè)字母 。文件總長(zhǎng)度不超過32K至少有一行數(shù)據(jù)。輸出僅包含一個(gè)整數(shù)該整數(shù)為單詞列表對(duì)應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)。時(shí)空限制1s / 64MB樣例輸入A AN ASP AS ASC ASCII BAS BASIC樣例輸出13代碼#includebits/stdc.husingnamespacestd;constintN1e510;intn;charop;string s;intson[N][30],cnt[N],idx;voidinsert(string str){intp0;for(inti0;istr.size();i){intustr[i]-a;if(!son[p][u])son[p][u]idx;pson[p][u];}cnt[p];}intquery(string str){intp0;for(inti0;istr.size();i){intustr[i]-a;if(!son[p][u])return0;pson[p][u];}returncnt[p];}intmain(){cinn;while(n--){cinops;if(opI)insert(s);elsecoutquery(s)endl;}return0;}結(jié)果