Tire樹/字典樹（HDU1251 POJ2503)

參考：https://blog.csdn.net/qq_43333395/article/details/89289170

什麼是字典樹

字典樹是一種資料結構,用于處理大量字元串.,優點在于利用字元串的公共字首,在存儲時節約存儲空間,并在查詢時最大限度的減少無謂的字元串比較.

HDU1251

字典的定義：

struct tire{//字典樹定義 
 tire* next[26];
 int num;//根據題意而定，以目前字元串為字首的單詞的數量 
 tire(){
  for(int i=0;i<26;i++)
   next[i]=NULL;
  num=0;
 }
};
           

插入：

tire root;
void insert(char word[]){//将字元串word插入到字典樹中 
 tire *p=&root;
 for(int i=0;word[i];i++){
  if(p->next[word[i]-'a']==NULL){
   p->next[word[i]-'a']=new tire;
  } 
  p=p->next[word[i]-'a'];
  p->num++;
 }
}
           

結果：

int find(char word[]){//傳回以字元串word為字首的單詞的數量 
 tire *p=&root;
 for(int i=0;word[i];i++){
  if(p->next[word[i]-'a']==NULL)
   return 0;
  p=p->next[word[i]-'a'];
 }
 return p->num;
}
           

int main(){
 char word[11];
 while(cin.getline(word,12)){//輸入單詞 
  if(strlen(word)==0||word[0]==' ') break;
  insert(word);
 }
 while(scanf("%s",word)!=EOF){
  printf("%d\n",find(word));
 }
 return 0;
}
           

POJ 2503

struct tire{//字典樹定義 
 tire* next[26];
 char* trans;//根據題意而定，以目前字元串為字首的單詞的數量 
 tire(){
  for(int i=0;i<26;i++)
   next[i]=NULL;
  trans=NULL;
 }
};
tire root;
void insert(char word[],char tran[]){//将字元串word插入到字典樹中 
 tire *p=&root;
 for(int i=0;word[i];i++){
  if(p->next[word[i]-'a']==NULL){
   p->next[word[i]-'a']=new tire;
  } 
  p=p->next[word[i]-'a'];
 }
 p->trans=new char[11];
 strcpy(p->trans,tran);
}
           

void find(char word[]){//傳回以字元串word為字首的單詞的數量 
 tire *p=&root;
 for(int i=0;word[i];i++){
  if(p->next[word[i]-'a']==NULL){
   cout<<"eh"<<endl;
   return;
  }
  p=p->next[word[i]-'a'];
 }
 if(p->trans!=NULL) 
  cout<<p->trans<<endl;
 else cout<<"eh"<<endl;
}
           

int main(){
 char tran[11],word[11],str[11];
 while(gets(str)){
  if(str[0]=='\0') break;
  sscanf(str,"%s%s",tran,word);
  insert(word,tran); 
 }
 while(scanf("%s",str)!=EOF){
  find(str);
 }
 return 0;
}
           

注意輸入格式：*

while(gets(str)){
  if(str[0]=='\0') break;
  sscanf(str,"%s%s",tran,word);
  insert(word,tran); 
 }