題目1337【例3-2】單詞查找樹題目描述在進行文法分析的時候通常需要檢測一個單詞是否在我們的單詞列表里。為了提高查找和定位的速度通常都畫出與單詞列表所對應(yīng)的單詞查找樹其特點如下1根結(jié)點不包含字母除根結(jié)點外每一個結(jié)點都僅包含一個大寫英文字母2從根結(jié)點到某一結(jié)點路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列稱為該結(jié)點對應(yīng)的單詞。單詞列表中的每個單詞都是該單詞查找樹某個結(jié)點所對應(yīng)的單詞3在滿足上述條件下該單詞查找樹的結(jié)點數(shù)最少。4例下圖左邊的單詞列表就對應(yīng)于右邊的單詞查找樹。注意對一個確定的單詞列表請統(tǒng)計對應(yīng)的單詞查找樹的結(jié)點數(shù)包含根結(jié)點。輸入為一個單詞列表每一行僅包含一個單詞和一個換行/回車符。每個單詞僅由大寫的英文字母組成長度不超過63個字母 。文件總長度不超過32K至少有一行數(shù)據(jù)。輸出僅包含一個整數(shù)該整數(shù)為單詞列表對應(yīng)的單詞查找樹的結(jié)點數(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é)果