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