poj 2001 Shortest Prefixes(trie 트리)

제목 링크: 클릭하여 링크 열기
사전 트리 템플릿 문제
노드에num을 추가하면 몇 개의 단어가 이 노드를 통과했는지 나타냅니다. 출력할 때num이 1이면 이 단어만 이곳을 통과할 수 있습니다break.
틀은 트리 - 해자 이 안에
코드에서 검색 함수 주석은 원 템플릿의 본제가 변경되었습니다
코드:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define MAX 26
using namespace std;

typedef struct TrieNode                     //Trie    
{
    bool isStr;                            //            
    struct TrieNode *next[MAX];         //    
    int num;
}Trie;

void insert(Trie *root,const char *s)     //   s       
{
    if(root==NULL||*s=='\0')
        return;
    int i;
    Trie *p=root;
    while(*s!='\0')
    {
        if(p->next[*s-'a']==NULL)        //     ，     
        {
            Trie *temp=(Trie *)malloc(sizeof(Trie));
            for(i=0;i<MAX;i++)
            {
                temp->next[i]=NULL;
            }
            temp->num=0;
            temp->isStr=false;
            p->next[*s-'a']=temp;
            p=p->next[*s-'a'];
            p->num++;
        }
        else
        {
            p=p->next[*s-'a'];
            p->num++;
        }
        s++;
    }
    p->isStr=true;                       //                   
}

void search(Trie *root,const char *s)  //            
{
    Trie *p=root;
    while(p!=NULL)
    {
        p=p->next[*s-'a'];
        printf("%c",*s);
        if(p->num==1){ printf("
"); break; }
        s++;
        if(*s=='\0'){ printf("
"); break; }
    }
}

void del(Trie *root)                      //             
{
    int i;
    for(i=0;i<MAX;i++)
    {
        if(root->next[i]!=NULL)
        {
            del(root->next[i]);
        }
    }
    free(root);
}

int main(){
    char t[1005][25];
    Trie *root= (Trie*)malloc(sizeof(Trie));
    for(int i=0;i<MAX;i++){
        root->next[i]=NULL;
    }
    int len=1;
    while(~scanf("%s",t[len])){
        insert(root,t[len++]);
    }

    for(int i=1;i<len;i++){
        printf("%s ",t[i]);
        search(root,t[i]);
    }

    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

BZOJ 12 HNOI 2004 L 언어 AC 자동기(Trie 트리) + 동적 기획

제목 대의: 단어표와 m개의 문자열을 정하여 모든 문자열의 가장 긴 접두사를 묻는다. 이 접두사를 만족시키면 일부 문자열로 나누어 이 문자열이 단어표에 나타난 적이 있다. 더 이상 데이터 범위를 잘못 보지 못하겠어....

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj 2001 Shortest Prefixes(trie 트리)

좋은 웹페이지 즐겨찾기